Source code online books for professionals by professionals

Listing 9-7.  The Floyd-Warshall Algorithm
def floyd_warshall(G):
    D, P = deepcopy(G), {}
    for u in G:
        for v in G:
            if u == v or G[u][v] == inf:
                P[u,v] = None
            else:
                P[u,v] = u
    for k in G:
        for u in G:
            for v in G:
                shortcut = D[u][k] + D[k][v]
                if shortcut < D[u][v]:
                    D[u][v] = shortcut
                    P[u,v] = P[k,v]
    return D, P
 
Note that it’s important to use shortcut < D[u][v] here, and not shortcut <= D[u][v]. Although the latter would 
still give the correct distances, you could get cases where the last step was D[v][v], which would lead to P[u,v] = None.
The Floyd-Warshall algorithm can quite easily be modified to calculate the transitive closure of a graph  
(Warshall’s algorithm). See Exercise 9-9.

---

Chapter 9 
■
 From a to B with edsger and Friends
201
Meeting in the Middle
The subproblems solutions of Dijkstra’s algorithm—and of BFS, its unweighted special case—spread outward on a graph 
like ripples on a pond. If all you want is getting from A to B, or, using the customary node names, from s to t, this means 
that the “ripple” has to pass many nodes that you’re not really interested, as in the left image in Figure 
9-4
. If, on the other 
hand, you start traversing from both your starting point and your end point (assuming you can traverse edges in reverse), 
the two ripples can, in some cases, meet up in the middle, saving you a lot of work, as illustrated in the right image.