+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
+ # Distance[t] is the shortest distance from source to t, using
+ # at most count edges. Parents[t] is the parnet link in the path
+ has_negative_cycle = False
+ # Each iteration is a "phase" of the algorithm.
+ # build up a new 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
+ 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
+ return distance, parents, has_negative_cycle
+ from graphs import Edge
+ pprint.pprint(bellman_ford(g, 4))
+if __name__ == "__main__":