Skip to content

Instantly share code, notes, and snippets.

@dpapathanasiou
Created April 20, 2019 20:23
Show Gist options
  • Save dpapathanasiou/9faebc117530bda8a526bfda29428fb2 to your computer and use it in GitHub Desktop.
Save dpapathanasiou/9faebc117530bda8a526bfda29428fb2 to your computer and use it in GitHub Desktop.
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