+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

+ new_queue.append(edge.w)

+ 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

+ g.add_edge(Edge(v,w,d))

+ pprint.pprint(bellman_ford(g, 4))

+if __name__ == "__main__":