Source code online books for professionals by professionals

Listing 9-6.  The Floyd-Warshall Algorithm, Distances Only
def floyd_warshall(G):
    D = deepcopy(G)                             # No intermediates yet
    for k in G:                                 # Look for shortcuts with k
        for u in G:
            for v in G:
                D[u][v] = min(D[u][v], D[u][k] + D[k][v])
    return D
 
You’ll notice that I start out using a copy of the graph itself as a candidate distance map. That’s because we 
haven’t tried to go via any intermediate nodes yet, so the only possibilities are direct edges, given by the original 
weights. Also notice that the assumption about the vertices being numbers is completely gone because we no 
longer need to explicitly parametrize which stage we’re in. As long as we try creating shortcuts with each possible 
intermediate node, building on our previous results, the solution will be the same. I hope you’ll agree that the 
resulting algorithm is super-simple, although the reasoning behind it may not be.
It would be nice to have a P matrix too, though, as in Johnson’s algorithm. As in so many DP algorithms, 
constructing the actual solution piggybacks nicely on calculating the optimal value—you just need to record which 
choices are made. In this case, if we find a shortcut via k, the predecessor recorded in P[u][v] must be replaced with 
P[k][v], which is the predecessor belonging to the last “half” of the shortcut. The final algorithm can be found in 
Listing 9-7. The original P gets a predecessor for any distinct pair of nodes linked by an edge. After that, P is updated 
whenever D is updated.