Source code online books for professionals by professionals

Listing 9-2.  The Bellman-Ford Algorithm
def bellman_ford(G, s):
    D, P = {s:0}, {}                            # Zero-dist to s; no parents
    for rnd in G:                               # n = len(G) rounds
        changed = False                         # No changes in round so far
        for u in G:                             # For every from-node...

---

Chapter 9 
■
 From a to B with edsger and Friends
191
            for v in G[u]:                      # ... and its to-nodes...
                if relax(G, u, v, D, P):        # Shortcut to v from u?
                    changed = True              # Yes! So something changed
        if not changed: break                   # No change in round: Done
    else:                                       # Not done before round n?
        raise ValueError('negative cycle')      # Negative cycle detected
    return D, P                                 # Otherwise: D and P correct
 
Note that this implementation of the Bellman-Ford algorithm differs from many presentations precisely in that 
it includes the changed check. That check gives us two advantages. First, it lets us terminate early, if we don’t need all 
the iterations; second, it lets us detect whether any change occurred during the last “superfluous” iteration, indicating 
a negative cycle. (The more common approach, without this check, is to add a separate piece of code implementing 
this last iteration, with its own change check.)
Because this algorithm is the foundation for several others, let’s make sure it’s clear how it works. Consider the 
weighted graph example from Chapter 2. We can specify it as a dict of dicts, as follows:
 
a, b, c, d, e, f, g, h = range(8)
G = {
    a: {b:2, c:1, d:3, e:9, f:4},
    b: {c:4, e:3},
    c: {d:8},
    d: {e:7},
    e: {f:5},
    f: {c:2, g:2, h:2},
    g: {f:1, h:6},
    h: {f:9, g:8}
}
 
See Figure 
9-1
 for a visual presentation of the graph. Let’s say we call bellman_ford(G, a). What happens? If we 
want to find out in more detail, we can use a debugger, or perhaps the trace or logging packages. For simplicity, let’s 
say we add a couple of print statements that show us the edges that are relaxed, as well as the assignments to D, if any. 
Let’s say we also iterate over the nodes and neighbors in sorted order (using sorted), for deterministic results.