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

• 4 9
• 0 7
• 2 5

Output 1

TRUE

0

6

9

2

11

INFINITY

Input 2

6 11

0 1 6

1 2 5

1 3 -4

• 4 8
• 1 -2

3 0 2

3 2 7

3 4 9

• 5 -14
• 0 7
• 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.