Skip to content

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.

Copy link

devinshields commented May 21, 2013

nice, thanks

@mahaalkhairy

This comment has been minimized.

Copy link

mahaalkhairy commented Jul 20, 2014

how do u run it?

@daixtr

This comment has been minimized.

Copy link

daixtr commented Sep 28, 2015

nope.. does not work

@lkettle

This comment has been minimized.

Copy link

lkettle commented Nov 19, 2015

beautiful, thank you

@suman1791

This comment has been minimized.

Copy link

suman1791 commented Mar 10, 2016

how do you run it ?

@Dxnielx

This comment has been minimized.

Copy link

Dxnielx commented Apr 18, 2016

how do you run it ?

@Carolyne121

This comment has been minimized.

Copy link

Carolyne121 commented May 8, 2016

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

@Mouna-Dhaouadi

This comment has been minimized.

Copy link

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.

Copy link

gfxcc commented Jul 2, 2017

Concise code.

@zhangzhiqiangcs

This comment has been minimized.

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

This comment has been minimized.

Copy link

chankongching commented Mar 14, 2019

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.