-
-
Save joninvski/701720 to your computer and use it in GitHub Desktop.
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() |
I have problems with running it, what can I do?
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
Concise code.
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~
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
how do you run it ?