Test yourself
Consider the following graph..
After the first iteration, what are the distances to the nodes 1, 3 and 5 respectively
How many negative edge cycles are present in the graph ?
What does it do ?
Bellman-Ford's algorithm helps compute the minimum spanning tree of a directed graph, which can have negative edges and negative edge cycles
If there is a cycle in the graph shose sum of edges in negative, then say djikstra's algorithm would keep going in an infinite loop as every time it runs the distance keeps getting shorter and shorter on adding the cycle.
IN the above graph, 1->3>2 forms a negative edge cycle.
What's the idea ?
1) Choose the starting vertex from where you want to calculate the distance to every other node. In the beginning, initialize the distance from the starting node to every node except itself to be infinity. The distance of the node from itself would be zero.
2) Now go through every edge - this can be done by going to every vertex and considering all its outgoing edges
For every edge A-B,
if dist[B] > dist[A] + length of AB,
dist[B] = dist[A] + length of AB
3) If there are V vertices, perform step 2 V-1 times, as there can br maximum V-1 edges in a pth and this will ensure that all distances have been updated to the latest values.
4) It is important to detect and report if the graph contains a negative edge cycle.
To do this, for every edge AB we check if dist[A] > dist[B] + length of AB.
If that is the case, it appears the distance decreased even after being finalized, which means there is a negative edge cycle inducing an infinite loop and infinite distance decrement. In this case we report the presence of a negative edge cycle.