Source code online books for professionals by professionals

Listing 9-5.  A Memoized Recursive Implementation of the Floyd-Warshall Algorithm
def rec_floyd_warshall(G):                                # All shortest paths
    @memo                                                 # Store subsolutions
    def d(u,v,k):                                         # u to v via 1..k
        if k==0: return G[u][v]                           # Assumes v in G[u]
        return min(d(u,v,k-1), d(u,k,k-1) + d(k,v,k-1))   # Use k or not?
    return {(u,v): d(u,v,len(G)) for u in G for v in G}   # D[u,v] = d(u,v,n)
 
Let’s have a go at an iterative version. Given that we have three subproblem parameters (u, v, and k), we’ll need 
three for loops to get through all the subproblems iteratively. It might seem reasonable to think that we need to store 
all subsolutions, leading to cubic memory use, but just like for the LCS problem, we can reduce this.
8
 Our recursive 
decomposition only relates problems in stage k with those in stage k−1. This means that we need only two distance 
maps—one for the current iteration and one for the previous. But we can do better ...
Just like when using relax, we’re looking for shortcuts here. The question at stage k is “Will going via node k provide 
a shortcut, compared to what we have?” If D is our current distance map and C is the previous one, we’ve got this:
 
D[u][v] = min(D[u][v], C[u][k] + C[k][v])
 
Now consider what would happen if we just used a single distance map throughout:
 
D[u][v] = min(D[u][v], D[u][k] + D[k][v])
 
The meaning is now slightly less clear and seemingly a bit circular, but there’s no problem, really. We’re looking 
for shortcuts, right? The values D[u][k] and D[k][v] will be the lengths of real paths (and therefore upper bounds 
to the shortest distances), so we’re not cheating. Also, they’ll be no greater than C[u][k] and C[k][v], because we 
never increase the values in our map. Therefore, the only thing that can happen is that D[u][v] moves faster toward 
the correct answer—which is certainly no problem. The result is that we need only a single, two-dimensional distance 
8
You could do the same memory saving in the memoized version, too. See Exercise 9-7.

---

Chapter 9 
■
 From a to B with edsger and Friends
200
map (that is, quadratic as opposed to cubic memory), which we’ll keep updating by looking for shortcuts. In many 
ways, the result is very much (though not exactly) like a two-dimensional version of the Bellman-Ford algorithm  
(see Listing 9-6).