# Commits

committed 9df8110

• Participants
• Parent commits 6c8987b

# File bellman_ford.py

`+import graphs`
`+`
`+def bellman_ford(graph, source):`
`+    """`
`+    Find shortest paths from a single source with possible negative`
`+    cycles.  Returns distances, parent links, and has_negative_cycle`
`+    """`
`+`
`+    V = graph.number_vertices`
`+`
`+    distance = [1e300 for x in graph.vertices]`
`+    distance[source] = 0`
`+    parents = [-1 for x in graph.vertices]`
`+    parents[source] = source`
`+    count = 0`
`+    # Distance[t] is the shortest distance from source to t, using`
`+    # at most count edges. Parents[t] is the parnet link in the path`
`+    # from source to t.`
`+`
`+    queue = [source]`
`+`
`+    has_negative_cycle = False`
`+    while queue:`
`+        # Each iteration is a "phase" of the algorithm. `
`+        count += 1`
`+        # build up a new queue.`
`+        new_queue = []`
`+        for v in queue:`
`+            for edge in graph.get_edge_iterator(v):`
`+                # distance[edge.w] is the current best to w with at`
`+                # most count edges.  If we go through v instead,`
`+                # we will have count edges.`
`+`
`+                d = edge.d + distance[v]`
`+                if d < distance[edge.w]:`
`+                    print "updating", edge.w, "to ", d`
`+                    distance[edge.w] = d`
`+                    parents[edge.w] = v`
`+                    new_queue.append(edge.w)`
`+        `
`+`
`+`
`+        queue = new_queue`
`+        if count == V and queue:`
`+            # The longest paths have V edges.  If a vertex still`
`+            # has a shorter path, then we have a negative cyle.`
`+            has_negative_cycle = True`
`+            break`
`+    return distance, parents, has_negative_cycle`
`+def test1():`
`+    import pprint`
`+    from graphs import Edge`
`+    g = graphs.Graph(6)`
`+    edges = [(0,1,41),`
`+             (0,5,29),`
`+             (1,2,51),`
`+             (1,4,52),`
`+             (2,3,50),`
`+             (3,5,-38),`
`+             (3,0,45),`
`+             (4,2,32),`
`+             (4,3,16),`
`+             (5,1,-29),`
`+             (5,4,21)]`
`+    for v,w,d in edges:`
`+        g.add_edge(Edge(v,w,d))`
`+`
`+    pprint.pprint(bellman_ford(g, 4))`
`+    `
`+if __name__ == "__main__":`
`+    test1()`
`+    `

# File graphs.py

` """Python implementation of code and problems from Sedgewick's`
` "Algorithms in C++, Part5".`
` `
`-`
` """`
` `
` `
` class Edge(object):`
`-    def __init__(self, v, w):`
`+    def __init__(self, v, w, d = 0):`
`         self.v, self.w = v, w`
`+        self.d = d`
`     def __repr__(self):`
`         return "%d-%d" % (self.v, self.w)`
`     `