Shortest path problem is problem of finding shortest path from given particular point/vertex to all other points or vertices in a graph. Bellman Ford algorithm is used for this purpose specially in the case of negative edge weight/weights in a graph. The only limitation of this algorithm is “graph should not contain negative edge weight cycles”, however the Bellman Ford algorithm can be used to detect negative edge cycles in graph.

Negative edge cycle example

Shortest path problem with negative weights  Bellman Ford algorithm

The above example graph contains a negative cycle in it. The negative  cycle is (2>3>4>2) because total sum of edge weight  becomes negative (-2 + 3 -3 ) = -2 . As in above graph the distance from (vertex 0) to (vertex 2) is 3 but if we go through the cycle (2>3>4>2) once , the total cost to reach from (vertex 0) to (vertex 2) will reduce to ( 3 -2 ) = 1. if we go through the cycle in second time the total cost to reach from (vertex 0) to (vertex 2) will become (1 – 2) = -1, which is less than the previous cost. if we continue to go through the cycle again and again then after each iteration cost to travel from (vertex 0) to (vertex 2) will reduced. In this case it is impossible to reach from (vertex 0) to (vertex 3).

Bellman Ford algorithm

Shortest path problem with negative weights  Bellman Ford algorithm

Sample code Shortest path problem with negative weights  Bellman Ford algorithm

Output:

Node 0    Node 1    Node 2    Node 3    Node 4    Node 5
———————————————————————–
0             5             3             1              4             4