Source code online books for professionals by professionals

Listing 9-9.  The Bidirectional Version of Dijkstra’s Algorithm
from itertools import cycle
 
def bidir_dijkstra(G, s, t):
    Ds, Dt = {}, {}                              # D from s and t, respectively
    forw, back = idijkstra(G,s), idijkstra(G,t)  # The "two Dijkstras"
    dirs = (Ds, Dt, forw), (Dt, Ds, back)        # Alternating situations
    try:                                         # Until one of forw/back ends
        for D, other, step in cycle(dirs):       # Switch between the two
            v, d = next(step)                    # Next node/distance for one
            D[v] = d                             # Remember the distance
            if v in other: break                 # Also visited by the other?
    except StopIteration: return inf             # One ran out before they met
    m = inf                                      # They met; now find the path
    for u in Ds:                                 # For every visited forw-node
        for v in G[u]:                           # ... go through its neighbors
            if not v in Dt: continue             # Is it also back-visited?
            m = min(m, Ds[u] + G[u][v] + Dt[v])  # Is this path better?
    return m                                     # Return the best path
 
Note that this code assumes that G is undirected (that is, all edges are available in both directions) and that  
G[u][u] = 0 for all nodes u. You could easily extend the algorithm so those assumptions aren’t needed (Exercise 9-12).
Knowing Where You’re Going
By now you’ve seen that the basic idea of traversal is pretty versatile, and by simply using different queues, you get 
several useful algorithms. For example, for FIFO and LIFO queues, you get BFS and DFS, and with the appropriate 
priorities, you get the core of Prim’s and Dijkstra’s algorithms. The algorithm described in this section, called A*, 
extends Dijkstra’s, by tweaking the priority once again.
As mentioned earlier, the A* algorithm uses an idea similar to Johnson’s algorithm, although for a different 
purpose. Johnson’s algorithm transforms all edge weights to ensure they’re positive, while ensuring that the shortest 
paths are still shortest. In A*, we want to modify the edges in a similar fashion, but this time the goal isn’t to make the 
edges positive—we’re assuming they already are (as we’re building on Dijkstra’s algorithm). No, what we want is to 
guide the traversal in the right direction, by using information of where we’re going: We want to make edges moving 
away from our target node more expensive than those that take us closer to it.
Note
 
■
  this is similar to the best-first search used in the branch and bound strategy discussed in Chapter 11.
Of course, if we really knew which edges would take us closer, we could solve the whole problem by being greedy. 
We’d just move along the shortest path, taking no side routes whatsoever. The nice thing about the A* algorithm is 
that it fills the gap between Dijkstra’s, where we have no knowledge of where we’re going, and this hypothetical, ideal 

---

Chapter 9 
■
 From a to B with edsger and Friends
204
situation where we know exactly where we’re going. It introduces a potential function, or heuristic h(v), which is our 
best guess for the remaining distance, d(v,t). As you’ll see in a minute, Dijkstra’s algorithm “falls out” of A* as a special 
case, when h(v) = 0. Also, if by magic we could set h(v) = d(v,t), the algorithm would march directly from s to t.
So, how does it work? We define the modified edge weights to get a telescoping sum, like we did in Johnson’s 
algorithm (although you should note that the signs are switched here): w’(u,v) = w(u,v) - h(u) + h(v). The telescoping 
sum ensures that the shortest path will still be shortest (like in Johnson’s) because all path lengths are changed by 
the same amount, h(t) - h(s). As you can see, if we set the heuristic to zero (or, really, any constant), the weights are 
unchanged.
It should be easy to see how this adjustment reflects our intention to reward edges that go in the right direction 
and penalize those that don’t. To each edge weight, we add the drop in potential (the heuristic), which is similar to 
how gravity works. If you let a marble loose on a bumpy table, it will start moving in a direction that will decrease its 
potential (that is, its potential energy). In our case, the algorithm will be steered in directions that cause a drop in the 
remaining distance—exactly what we want.
The A* algorithm is equivalent to Dijkstra’s on the modified graph, so it’s correct if h is feasible, meaning that 
w’(u,v) is nonnegative for all nodes u and v. Nodes are scanned in increasing order of D[v] - h(s) + h(v), rather than 
simply D[v]. Because h(s) is a common constant, we can ignore it and simply add h(v) to our existing priority. This 
sum is our best estimate for the shortest path from s to t via v. If w’(u,v) is feasible, h(v) will also be a lower bound on 
d(v,t) (see Exercise 9-14).
One (very common) way of implementing all of this would be to use something like the original dijkstra and 
simply add h(v) to the priority when pushing a node onto the heap. The original distance estimate would still be 
available in D. If we want to simplify things, however, only using the heap (as in idijkstra), we need to actually use 
the weight adjustment so that for an edge (u,v), we subtract h(u) as well. This is the approach I’ve taken in Listing 9-10.  
As you can see, I’ve made sure to remove the superfluous h(t) before returning the distance. (Considering the 
algorithmic punch that the a_star function is packing, it’s pretty short and sweet, wouldn’t you say?)