Commits

David Jones committed ebe352d

got rid of multiple queues

Comments (0)

Files changed (1)

 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:
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.