Commits

David Jones  committed 9df8110

added bellman-ford

  • Participants
  • Parent commits 6c8987b

Comments (0)

Files changed (2)

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()
+    
 """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)