you need to implement the Dijkstra and Bellman Ford algorithms to solve the Single Source Shortest Path problem.
Input/Output:
You will take input from an input file and give output to an output file.
Input Format:
The graph is directed .
The first line has two space-separated integers N and M , the number of nodes and edges in the graph.
In the next M lines, there will be three space-separated integers u , v, and w denoting an edge where u and v denote the starting and ending nodes and w denotes the weight of the directed edge.
You need to find the distance and path between the source and destination which will be given in the next line as two space separated integers S and D , the source and destination.
Output Format:
In the first line of the output file, you need to print the distance between the source and the destination as a single integer.
In the next line, you need to print the path between the source and the destination separating the nodes with “-> ”.
For Bellman Ford algorithm, you need to detect negative weight cycles as well.
See the sample I/O for further clarification.
Constraints:
1 < N ≤ 1000
1 < M ≤ N * (N − 1) / 2
0 ≤ u, v < N
0 ≤ S, D < N
− 100000 ≤ w ≤ 100000(for Dijkstra, consider |w|)
Sample I/O:
Input
Output
9 17
0 7 60
7 1 -150
4 8 -70
6 4 80
5 1 4000
8 0 100000
2 3 -200
8 2 1000
0 3 300
3 8 50000
3 7 -200 2 5 120
6 3 1500
4 0 90
5 7 -50
1 6 100
4 1 -90
0 5
Bellman Ford Algorithm:
1140
0 -> 7 -> 1 -> 6 -> 4 -> 8 -> 2 -> 5
Dijkstra Algorithm:
1580
0 -> 7 -> 1 -> 6 -> 4 -> 8 -> 2 -> 5
