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 -4 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 -3 relaxing edge (2, 0) with d[0] going from -1 to -2 d= [-2, 1, -3, 2, 0] p= [2, 0, 1, 0, None] relaxing edge (0, 1) with d[1] going from 1 to 0 relaxing edge (0, 3) with d[3] going from 2 to 1 relaxing edge (1, 2) with d[2] going from -3 to -4 relaxing edge (2, 0) with d[0] going from -2 to -3 d= [-3, 0, -4, 1, 0] p= [2, 0, 1, 0, None] relaxing edge (0, 1) with d[1] going from 0 to -1 relaxing edge (0, 3) with d[3] going from 1 to 0 relaxing edge (1, 2) with d[2] going from -4 to -5 relaxing edge (2, 0) with d[0] going from -3 to -4 d= [-4, -1, -5, 0, 0] p= [2, 0, 1, 0, None] negCycles= True