Source code online books for professionals by professionals

Listing 8-3.  Recursive, Memoized DAG Shortest Path
def rec_dag_sp(W, s, t):                        # Shortest path from s to t
    @memo                                       # Memoize f
    def d(u):                                   # Distance from u to t
        if u == t: return 0                     # We're there!
        return min(W[u][v]+d(v) for v in W[u])  # Best of every first step
    return d(s)                                 # Apply f to actual start node
 
In my opinion, the implementation in Listing 8-3 is quite elegant. It directly expresses the inductive idea of the 
algorithm, while abstracting away the memoization. However, this is not the classical way of expressing this algorithm. What 
is customarily done here, as in so many other DP algorithms, is to turn the algorithm “upside down” and make it iterative.
The iterative version of the DAG shortest path algorithm works by propagating partial solutions step by step, 
using the relaxation idea introduced in Chapter 4.
9
 Because of the way we represent graphs (that is, we usually access 
nodes by out-edges, rather than in-edges), it can be useful to reverse the inductive design: Instead of thinking about 
where we want to go, we think about where we want to come from. Then we want to make sure that once we reach a 
node v, we have already propagated correct answers from all v’s predecessors. That is, we have already relaxed its  
in-edges. This raises the question—how can we be sure we’ve done that?
The way to know is to sort the nodes topologically, as they are in Figure 
8-3
. The neat thing about the recursive 
version (in Listing 8-3) is that no separate topological sorting is needed. The recursion implicitly performs a DFS and 
does all updates in topologically sorted order automatically. For our iterative solution, though, we need to perform a 
separate topological sorting. If you want to get away from the recursion entirely, you can use topsort from Listing 4-10;  
if you don’t mind, you could use dfs_topsort from Listing 5-7 (although then you’re already quite close to the 
memoized recursive solution). The function dag_sp in Listing 8-4 shows you this more common, iterative solution.