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]