Source code online books for professionals by professionals

Figure 9-5.  The first meeting point (highlighted node) is not necessarily along the shortest path (highlighted edge)
In fact, ending the traversal once the two instances meet is fine. To find the shortest path, however, we need 
to keep our eyes peeled, metaphorically speaking, while the algorithm is executing. We need to maintain the best 
distance found so far, and whenever an edge (u,v) is relaxed and we already have the distance to u from s (by forward 
traversal) and the distance from v to t (by backward traversal), we need to check whether linking up the paths with 
(u,v) will improve on our best solution.
In fact, we can tighten our stopping criterion a bit (see Exercise 9-10). Rather than waiting for the two instances 
to both visit the same node, we need to look only at how far they’ve come—that is, the latest distances they’ve yielded. 
These can’t decrease, so if their sum is at least as great as the best path we’ve found so far, we can’t find anything 
better, and we’re done.
There’s still a nagging doubt, though. The preceding argument might convince you that we can’t possibly find any 
better paths by continuing, but how can we be sure that we haven’t missed any? Let’s say the best path we’ve found has 
length m. The two distances that caused the termination were l and r, so we know that l + r ³ m (the stopping criterion). 
Now, let’s say there is a path from s to t that is shorter than m. For this to happen, the path must contain an edge (u,v) such 
that d(s,u) < l and d(v,t) < r (see Exercise 9-11). This means that u and v are closer to s and t, respectively, than the current 
nodes, so both must have been visited (yielded) already. At the point when both had been yielded, our maintenance of the 
best solution so far should have found this path—a contradiction. In other words, the algorithm is correct.
This whole keeping track of the best path so far business requires us to have access to the innards of Dijkstra’s 
algorithm. I prefer the abstraction that idijkstra gives me, so I’m going to stick with the simplest version of this 
algorithm: Stop once I’ve received the same node from both traversals and then scan for the best path afterward, 

---

Chapter 9 
■
 From a to B with edsger and Friends
203
examining all the edges that link the two halves. If your data set is of the kind that would profit from the bidirectional 
search, this scan is unlikely to be too much of a bottleneck, but feel free to break out the profiler and make your 
adjustments, of course. The finished code can be found in Listing 9-9. The cycle function from itertools gives us 
an iterator that will repeatedly give us the values from some other iterator, repeatedly yielding its values from start to 
finish. In this case, this means we’re cycling between the forward and backward directions.