Description
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 6
1 2 5
1 3 -4
1 4 8
2 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.
