Instantly share code, notes, and snippets.

# joninvski/bellman.py Created Nov 16, 2010

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 commented May 21, 2013

 nice, thanks

### mahaalkhairy commented Jul 20, 2014

 how do u run it?

### daixtr commented Sep 28, 2015

 nope.. does not work

### lkettle commented Nov 19, 2015

 beautiful, thank you

### suman1791 commented Mar 10, 2016

 how do you run it ?

### Dxnielx commented Apr 18, 2016

 how do you run it ?

### Carolyne121 commented May 8, 2016

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

### 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 commented Jul 2, 2017

 Concise code.

### zhangzhiqiangcs commented Dec 2, 2017 • edited

 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 commented Mar 14, 2019

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