Source code online books for professionals by professionals

Listing 9-3.  Dijkstra’s Algorithm
from heapq import heappush, heappop
 
def dijkstra(G, s):
    D, P, Q, S = {s:0}, {}, [(0,s)], set()      # Est., tree, queue, visited
    while Q:                                    # Still unprocessed nodes?
        _, u = heappop(Q)                       # Node with lowest estimate
        if u in S: continue                     # Already visited? Skip it
        S.add(u)                                # We've visited it now
        for v in G[u]:                          # Go through all its neighbors
            relax(G, u, v, D, P)                # Relax the out-edge
            heappush(Q, (D[v], v))              # Add to queue, w/est. as pri
    return D, P                                 # Final D and P returned
 
Dijkstra’s algorithm may be similar to Prim’s (with another set of priorities for the queue), but it is also closely 
related to another old favorite: BFS. Consider the case where the edge weights are positive integers. Now, replace an 
edge that has weight w with w-1 unweighted edges, connecting a path of dummy nodes (see Figure 
9-3
). We’re ruining 
what chances we had for an efficient solution (see Exercise 9-3), but we know that BFS will find a correct solution. In 
fact, it will do so in a way very similar to Dijkstra’s algorithm: It will spend an amount of time on each (original) edge 
proportional to its weight, so it will reach each (original) node in order of distance from the start node.
a
b
3
a
b