Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# dpapathanasiou/bellman_ford.py

Created Apr 20, 2019
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' }
to join this conversation on GitHub. Already have an account? Sign in to comment