Created
November 16, 2010 11:31
-
-
Save joninvski/701720 to your computer and use it in GitHub Desktop.
Bellman ford python implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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() |
in some scenario i found AssertionError, recommend using https://gist.github.com/ngenator/6178728 just getting the same result
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
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~