Instructions:
Choose a graph, then click the buttons (or press the
← and → keys) to step through Bellman-Ford.
Each step is one call to update.
The number next to each node is its estimated distance from the
source, est, and the purple arrows point to each node from its
estimated predecessor. The edge being updated is drawn in bold.
One iteration updates every edge once; Bellman-Ford without
early stopping runs |V| − 1
iterations in total.
Remember that the order in which Bellman-Ford updates the edges is arbitrary, in the sense that the algorithm is guaranteed to find the correct shortest paths no matter what order the edges are updated in. However, if we use Bellman-Ford with early stopping, some orders of updates may converge to the correct distances faster than others. The order that the edges are updated in the demo is shown in the status line above the graph.
Bellman-Ford never knows which of its estimates are correct: nothing in
est says whether a number is final. What it does guarantee is
the loop invariant: after k iterations, every node whose actual
shortest path from the source has at most k edges is estimated
correctly. Check Mark correct estimates under Options to see which
estimates are already correct at each step, which is something the
algorithm itself can't see.