Source code online books for professionals by professionals

Figure 9-4.  Unidirectional and bidirectional “ripples,” indicating the work needed to find a path from s to t by traversal
Note that while the “graphical evidence” of Figure 
9-4
 may be convincing, it is, of course, not a formal 
argument, and it gives no guarantees. In fact, although the algorithms of this section and the next provide practical 
improvements for the single-source, single-destination shortest path, no such a point-to-point algorithm is known 
to have a better asymptotic worst-case behavior than you could get for the ordinary single-source problem. Sure, two 
circles of half the original radius will have half the total area, but graphs don’t necessarily behave like the Euclidean 
plane. We would certainly expect to get improvements in running time, but this is what’s called a heuristic algorithm. 
Such algorithms are based on educated guesswork and are typically evaluated empirically. We can be sure it won’t be 
worse than Dijkstra’s algorithm, asymptotically—it’s all about improving the practical running time.
To implement this bidirectional version of Dijkstra’s algorithm, let’s first adapt the original slightly, making it a 
generator, so we can extract only as many subsolutions as we need for the “meetup.” This is similar to some of the 
traversal functions in Chapter 5, such as iter_dfs (Listing 5-5). This iterative behavior means that we can drop the 
distance table entirely and rely only on the distances kept in the priority queue. To keep things simple, I won’t include 
the predecessor information here, but you could easily extend the solution by adding predecessors to the tuples in  
the heap. To get the distance table (like in the original dijkstra), you can simply call dict(idijkstra(G, s)).  
See Listing 9-8 for the code.