Source code online books for professionals by professionals

Listing 9-8.  Dijkstra’s Algorithm Implemented as a Generator
from heapq import heappush, heappop
 
def idijkstra(G, s):
    Q, S = [(0,s)], set()                       # Queue w/dists, visited
    while Q:                                    # Still unprocessed nodes?
        d, u = heappop(Q)                       # Node with lowest estimate
        if u in S: continue                     # Already visited? Skip it

---

Chapter 9 
■
 From a to B with edsger and Friends
202
        S.add(u)                                # We've visited it now
        yield u, d                              # Yield a subsolution/node
        for v in G[u]:                          # Go through all its neighbors
            heappush(Q, (d+G[u][v], v))         # Add to queue, w/est. as pri
 
Note that I’ve dropped the use of relax completely—it is now implicit in the heap. Or, rather, heappush is the new 
relax. Re-adding a node with a better estimate means it will take precedence over the old entry, which is equivalent to 
overwriting the old one with a relax operation. This is analogous to the implementation of Prim’s algorithm in Chapter 7.
Now that we have access to Dijkstra’s algorithm step by step, building a bidirectional version isn’t too hard.  
We alternate between the to and from instances of the original algorithm, extending each ripple, one node at a time. 
If we just kept going, this would give us two complete answers—the distance from s to t and the distance from t to s 
if we follow the edges backward. And, of course, those two answers would be the same, making the whole exercise 
pointless. The idea is to stop once the ripples meet. It seems like a good idea to break out of the loop once the two 
instances of idijkstra have yielded the same node.
This is where the only real wrinkle in the algorithm appears: You’re traversing from both s and t, consistently 
moving to the next closest node, so once the two algorithms have both moved to (that is, yielded) the same node, it 
would seem reasonable that the two had met along the shortest path, right? After all, if you were traversing only from s, 
you could terminate as soon as you reached (that is, idijkstra yielded) t. Sadly, as can so easily happen, our intuition 
(or, at least, mine) fails us here. The simple example in Figure 
9-5
 should clear up this possible misconception; but 
where is the shortest path, then? And how can we know it’s safe to stop?