Bellman Ford Algorithm

bellman_ford.py

#!/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'
}