Bellman-Ford algorithm for single-source shortest paths
LEGEND:
The square n x n matrix represents the graph and contains the weights
of the edges. It must have zeros on the diagonal. The symbol None here
stands for plus infinity (no edge). Vertices are implicitly named with
integers from 0 to n-1.
The single scalar value printed next is the index of the chosen
source vertex.
The n-element vector d contains distances: for each vertex, the best
shortest distance from the source found so far. As in the weights
matrix, here None means plus infinity (at this stage, we still don't
know how to reach this node from the source).
The n-element vector p contains vertex names: for each vertex, the
predecessor vertex along the shortest path found so far. Here, the
symbol None stands for the null pointer (no predecessor).
The boolean negCycles says whether the algorithm discovered any
negative-weight cycles reachable from the root. When this happens, the
other outputs from the algorithm (d and p) are undefined.
0 2 2 3 None
None 0 -3 None None
1 None 0 5 None
None None None 0 None
-1 None None 4 0
source vertex = 4
d= [None, None, None, None, 0]
p= [None, None, None, None, None]
relaxing edge (4, 0) with d[0] going from None to -1
relaxing edge (4, 3) with d[3] going from None to 4
d= [-1, None, None, 4, 0]
p= [4, None, None, 4, None]
relaxing edge (0, 1) with d[1] going from None to 1
relaxing edge (0, 2) with d[2] going from None to 1
relaxing edge (0, 3) with d[3] going from 4 to 2
relaxing edge (1, 2) with d[2] going from 1 to -2
d= [-1, 1, -2, 2, 0]
p= [4, 0, 1, 0, None]
d= [-1, 1, -2, 2, 0]
p= [4, 0, 1, 0, None]
d= [-1, 1, -2, 2, 0]
p= [4, 0, 1, 0, None]
negCycles= False