Source code online books for professionals by professionals

Listing 8-4.  DAG Shortest Path
def dag_sp(W, s, t):                            # Shortest path from s to t
    d = {u:float('inf') for u in W}             # Distance estimates
    d[s] = 0                                    # Start node: Zero distance
    for u in topsort(W):                        # In top-sorted order...
        if u == t: break                        # Have we arrived?
        for v in W[u]:                          # For each out-edge ...
            d[v] = min(d[v], d[u] + W[u][v])    # Relax the edge
    return d[t]                                 # Distance to t (from s)
 
The idea of the iterative algorithm is that as long as we have relaxed each edge out from each of your possible 
predecessors (that is, those earlier in topologically sorted order), we must necessarily have relaxed all the in-edges to 
you. Using this, we can show inductively that each node receives a correct distance estimate at the time we get to it in 
the outer for loop. This means that once we get to the target node, we will have found the correct distance.
Finding the actual path corresponding to this distance isn’t all that hard either (see Exercise 8-5). You could even 
build the entire shortest path tree from the start node, just like the traversal trees in Chapter 5. (You’d have to remove 
the break statement, though, and keep going till the end.) Note that some nodes, including those earlier than the start 
node in topologically sorted order, may not be reached at all and will keep their infinite distances.
9
This approach is also closely related to Prim’s and Dijkstra’s algorithms, as well as the Bellman-Ford algorithm  
(see Chapters 7 and 9).

---

Chapter 8 
■
 tangled dependenCies and MeMoization 
172
Note
 
■
  in most of this chapter, i focus on finding the optimal value of a solution, without the extra bookkeeping needed 
to reconstruct the solution that gives rise to that value. this approach makes the presentation simpler but may not be 
what you want in practice. some of the exercises ask you to extend algorithms to find the actual solutions; you can find 
an example of how to do this at the end of the section about the knapsack problem.