Dijkstra 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. If any edges are negative, the outputs of the algorithm are undefined. 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 list of pairs q is the priority queue holding the vertices still to be processed, keyed by best distance found so far and kept in the format (distance, vertex). The list done contains the vertices for which the shortest path has already been found. 0 None 3 None None 2 0 None None None 4 1 0 None None 10 None 5 0 None None None None None 0 source vertex = 3 d= [None, None, None, 0, None] p= [None, None, None, None, None] q= [(0, 3), (None, 0), (None, 1), (None, 2), (None, 4)] done= [] relaxing edge (3, 0) with d[0] going from None to 10 relaxing edge (3, 2) with d[2] going from None to 5 d= [10, None, 5, 0, None] p= [3, None, 3, None, None] q= [(5, 2), (10, 0), (None, 1), (None, 4)] done= [3] relaxing edge (2, 0) with d[0] going from 10 to 9 relaxing edge (2, 1) with d[1] going from None to 6 d= [9, 6, 5, 0, None] p= [2, 2, 3, None, None] q= [(6, 1), (9, 0), (None, 4)] done= [3, 2] relaxing edge (1, 0) with d[0] going from 9 to 8 d= [8, 6, 5, 0, None] p= [1, 2, 3, None, None] q= [(8, 0), (None, 4)] done= [3, 2, 1] d= [8, 6, 5, 0, None] p= [1, 2, 3, None, None] q= [(None, 4)] done= [3, 2, 1, 0] d= [8, 6, 5, 0, None] p= [1, 2, 3, None, None] q= [] done= [3, 2, 1, 0, 4]