+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]

# 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)

+ # Each iteration is a "phase" of the algorithm.

+ has_negative_cycle = True

+ 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