# Commits

committed ebe352d

got rid of multiple queues

• Participants
• Parent commits 9df8110

# bellman_ford.py

` import graphs`
`+from collections import deque`
` `
` 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]`
`     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]`
`+    queue = deque()`
`+    queue.append(V)`
`+    queue.append(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)`
`+    while True:`
`+        # Each iteration is a "phase" of the algorithm.`
`+`
`+        while queue[0] == V:`
`+            queue.popleft()`
`+            queue.append(V)`
`+            count += 1`
`+            if count > V:`
`+                if queue[0] != V:`
`+                    has_negative_cycle = True`
`+                break`
`+        if count > V:`
`+            break`
`+`
`+        v = queue.popleft()`
`         `
`+        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`
`+                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`
`              (3,5,-38),`
`              (3,0,45),`
`              (4,2,32),`
`-             (4,3,16),`
`+             (4,3,17),`
`              (5,1,-29),`
`              (5,4,21)]`
`     for v,w,d in edges:`