Rebrained!

Shortest Path – Python

Problem: Write a python function to calculate the shortest path given a start node (or vertex), an end node and a graph. Use Dijkstra’s algorithm. Return the distance from the start node to the end node, as well as the path taken to get there.

The implementation below sticks pretty closely to the algorithm description in the wikipedia entry, which I turned into something a little more pseudo-code-ish to help me implement it:

Initial state:

1. give nodes two properties – node.visited and node.distance
2. set node.distance = infinity for all nodes except the start node which is set to zero.
3. set node.visited = false for all nodes
4. set current node = start node.

Current node loop:

1. if current node = end node, finish and return current.distance & path
2. for all unvisited neighbors, calc their tentative distance (current.distance + edge to neighbor).
3. if tentative distance < neighbor's set distance, overwrite it.
4. set current.isvisited = true.
5. set current = remaining unvisited node with smallest node.distance

Here’s my implementation – it’s recursive, as suggested by the algorithm description:

import sys
def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
    """Find the shortest path between start and end nodes in a graph"""
    # detect if it's the first time through, set current distance to zero
    if not visited: distances[start]=0
    if start==end:
        # we've found our end node, now find the path to it, and return
        path=[]
        while end != None:
            path.append(end)
            end=predecessors.get(end,None)
        return distances[start], path[::-1]
    # process neighbors as per algorithm, keep track of predecessors
    for neighbor in graph[start]:
        if neighbor not in visited:
            neighbordist = distances.get(neighbor,sys.maxint)
            tentativedist = distances[start] + graph[start][neighbor]
            if tentativedist < neighbordist:
                distances[neighbor] = tentativedist
                predecessors[neighbor]=start
    # neighbors processed, now mark the current node as visited
    visited.append(start)
    # finds the closest unvisited node to the start
    unvisiteds = dict((k, distances.get(k,sys.maxint)) for k in graph if k not in visited)
    closestnode = min(unvisiteds, key=unvisiteds.get)
    # now we can take the closest node and recurse, making it current
    return shortestpath(graph,closestnode,end,visited,distances,predecessors)

if __name__ == "__main__":
    graph = {'a': {'w': 14, 'x': 7, 'y': 9},
            'b': {'w': 9, 'z': 6},
            'w': {'a': 14, 'b': 9, 'y': 2},
            'x': {'a': 7, 'y': 10, 'z': 15},
            'y': {'a': 9, 'w': 2, 'x': 10, 'z': 11},
            'z': {'b': 6, 'x': 15, 'y': 11}}
    print shortestpath(graph,'a','a')
    print shortestpath(graph,'a','b')

    """
    Result:
        (0, ['a'])
        (20, ['a', 'y', 'w', 'b'])
        """

You’ll see I turned the example in wikipedia into a graph for the test case in the code above.

I found this useful about how to represent and process graphs in python: http://www.python.org/doc/essays/graphs.html. I think this was written by Guido himself.

There’s a bunch of interesting implementations on the web, including two here. More elegant, but it took me a while to understand them.