Bellman Ford Algorithm
#!/usr/bin/env python | |
""" | |
An implementation of the Bellman-Form algorithm from: | |
"Python Algorithms: Mastering Basic Algorithms in the Python Language" | |
by Magnus Lie Hetland | |
ISBN: 9781484200551 | |
Input consists of a graph (dict) of { node: {neighbor: weight} } plus a source node. | |
Outputs the distances to each node, along with the set of parents. | |
""" | |
def bellman_ford (graph, src): | |
if not graph.has_key(src): | |
raise AttributeError("The source '%s' is not in the graph" % src) | |
# initialize the outputs | |
distances = {} | |
parents = {} | |
for node in graph: | |
distances[node] = float('inf') | |
parents[node] = None | |
distances[src] = 0 | |
for _ in xrange(len(graph)): | |
# iterate through each node | |
for node in graph.keys(): | |
for neighbor in graph[node]: | |
# relax: attempt to find a shorter path from node to neighbor, | |
# and if it exists, update the distances and parents accordingly | |
if distances[neighbor] > distances[node] + graph[node][neighbor]: | |
distances[neighbor] = distances[node] + graph[node][neighbor] | |
parents[neighbor] = node | |
# confirm there are no cycles | |
for node in graph.keys(): | |
for neighbor in graph[node]: | |
assert distances[neighbor] <= distances[node] + graph[node][neighbor] | |
return distances, parents | |
test = { | |
'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(test, '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' | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment