Instantly share code, notes, and snippets.

Embed
What would you like to do?
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()
@devinshields

This comment has been minimized.

devinshields commented May 21, 2013

nice, thanks

@mahaalkhairy

This comment has been minimized.

mahaalkhairy commented Jul 20, 2014

how do u run it?

@daixtr

This comment has been minimized.

daixtr commented Sep 28, 2015

nope.. does not work

@lkettle

This comment has been minimized.

lkettle commented Nov 19, 2015

beautiful, thank you

@suman1791

This comment has been minimized.

suman1791 commented Mar 10, 2016

how do you run it ?

@Dxnielx

This comment has been minimized.

Dxnielx commented Apr 18, 2016

how do you run it ?

@Carolyne121

This comment has been minimized.

Carolyne121 commented May 8, 2016

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

@Mouna-Dhaouadi

This comment has been minimized.

Mouna-Dhaouadi commented Nov 28, 2016

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

This comment has been minimized.

gfxcc commented Jul 2, 2017

Concise code.

@zhangzhiqiangcs

This comment has been minimized.

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~

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