The Bellman-Ford Algorithm
In this assignment, you are asked to implement the Bellman-Ford Algorithm which solves the single-source shortest-paths problem. Specifically, you are given as input a directed graph G = (V,E) with weight w(u,v) on each edge (u,v) ∈ E along with a source vertex s ∈ V . Edges may have negative weights.
Input The input has the following format. There are two integers on the first line. The first integer represents the number of vertices, |V |. The second integer is the number of edges, |E|. Vertices are indexed by 0,1,...,|V | − 1. Each of the following |E| lines has three integers u,v,w(u,v) , which represent an edge (u,v) with weight w(u,v). Vertex 0 is the source vertex.
Output The output falls into two possible cases.
Case (i): There is no negative-weight cycle reachable from s. In this case, you must output TRUE on the first line, followed by the shortest distance from s to each vertex in the graph. More precisely, you must output TRUE, δ(0,0), δ(0,1), ..., δ(0,|V | − 1), one per line. Recall that δ(u,v) denotes the shortest distance from u to v. If a vertex v is not reachable, output INFINITY in place of δ(0,v).
Case (ii): There is a negative-weight cycle reachable from s. You must output FALSE.
Examples of input and output
Input 1
6 10
0 1 61 2 51 3 -41 4 82 1 2
3 0 2
3 2 7
3 4 9
4 0 7
5 2 5
Output 1
TRUE
0
6
9
2
11
INFINITY
Input 2
6 11
0 1 6
1 2 5
1 3 -4
1 4 8
2 1 -2
3 0 2
3 2 7
3 4 9
3 5 -14
4 0 7
5 2 5
Output 2
FALSE
Note that every line is followed by an enter key.
See the lab guidelines for submission/grading, etc., which can be found in Files/Labs.
