Skip to content

Instantly share code, notes, and snippets.

@joninvski
Created November 16, 2010 11:31
Show Gist options
  • Save joninvski/701720 to your computer and use it in GitHub Desktop.
Save joninvski/701720 to your computer and use it in GitHub Desktop.
Bellman ford python implementation
import pdb
"""
The Bellman-Ford algorithm
Graph API:
iter(graph) gives all nodes
iter(graph[u]) gives neighbours of u
graph[u][v] gives weight of edge (u, v)
"""
# Step 1: For each node prepare the destination and predecessor
def initialize(graph, source):
d = {} # Stands for destination
p = {} # Stands for predecessor
for node in graph:
d[node] = float('Inf') # We start admiting that the rest of nodes are very very far
p[node] = None
d[source] = 0 # For the source we know how to reach
return d, p
def relax(node, neighbour, graph, d, p):
# If the distance between the node and the neighbour is lower than the one I have now
if d[neighbour] > d[node] + graph[node][neighbour]:
# Record this lower distance
d[neighbour] = d[node] + graph[node][neighbour]
p[neighbour] = node
def bellman_ford(graph, source):
d, p = initialize(graph, source)
for i in range(len(graph)-1): #Run this until is converges
for u in graph:
for v in graph[u]: #For each neighbour of u
relax(u, v, graph, d, p) #Lets relax it
# Step 3: check for negative-weight cycles
for u in graph:
for v in graph[u]:
assert d[v] <= d[u] + graph[u][v]
return d, p
def test():
graph = {
'a': {'b': -1, 'c': 4},
'b': {'c': 3, 'd': 2, 'e': 2},
'c': {},
'd': {'b': 1, 'c': 5},
'e': {'d': -3}
}
d, p = bellman_ford(graph, 'a')
assert d == {
'a': 0,
'b': -1,
'c': 2,
'd': -2,
'e': 1
}
assert p == {
'a': None,
'b': 'a',
'c': 'b',
'd': 'e',
'e': 'b'
}
if __name__ == '__main__': test()
@Dxnielx
Copy link

Dxnielx commented Apr 18, 2016

how do you run it ?

@Carolyne121
Copy link

I have problems with running it, what can I do?

@Mouna-Dhaouadi
Copy link

Be careful that the declaration
graph = {
'a': {'b': -1, 'c': 4},
'b': {'c': 3, 'd': 2, 'e': 2},
'c': {},
'd': {'b': 1, 'c': 5},
'e': {'d': -3}
}

coressponds to a dictionnary definition.
If you are using a Graph or a DiGraph, after declaring your Graph, use
d, p = bellman( G.to_dictionary() , source_node)
with G=your graph

@gfxcc
Copy link

gfxcc commented Jul 2, 2017

Concise code.

@zhangzhiqiangcs
Copy link

zhangzhiqiangcs commented Dec 2, 2017

I am not very clear that
for i in range(len(graph)-1): #Run this until is converges
what the fist for loop indicate ?
I'd be very appreciate it if anyone could tell me.
Thanks~

@chankongching
Copy link

in some scenario i found AssertionError, recommend using https://gist.github.com/ngenator/6178728 just getting the same result

@vapaternina
Copy link

in some scenario i found AssertionError, recommend using https://gist.github.com/ngenator/6178728 just getting the same result

Thanks

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment