Home Original page

Dijkstra's Shortest Path algorithm

Carey Evans c.evans at clear.net.nz
Sat Dec 9 17:36:07 EST 2000 
"Jürgen Hermann" <jh at web.de> writes:

> Maybe you should try to implement it in Python and NOT take 2-3 days. ;))
> 
> Tongue-in-cheek-ingly yours, Jürgen

Well...  I implemented it in Python last night and took 2-3 hours.  ;)

There's not much to it, so I'll post it here.  I'm putting this code
in the public domain, so you can do whatever you like with it.

----------------------------------------------------------------------
#!/usr/bin/python

# Andrew Snare's PQueue: http://www.pigpond.com/~earthpig/PQueue-0.1a.tar.bz2
import pqueue

# From Kingston, J. H., _Algorithms and Data Structures_, Addison Wesley, 1991.
data = { 'a': [('b', 13), ('c', 4), ('d', 7)],
         'b': [('a', 13), ('e', 1)],
         'c': [('a', 4), ('e', 7)],
         'd': [('a', 7), ('e', 2)],
         'e': [('b', 1), ('c', 7), ('d', 2)] }

# All shortest paths by Dijkstra's algorithm.
def all_shortest_paths(graph, start):
    # Previous node on current shortest path to start node.
    parents = {}

    # Current distance to start node.
    distances = {start: 0}

    # Which nodes we've seen - starts out with just the start node.
    visited = {}
    for v in graph.keys():
        visited[v] = 0
    visited[start] = 1

    # Set up priority queue with just the start node in it.
    pq = pqueue.PQueue()
    pq.insert(0, start)

    # Loop over closest nodes in queue until none left.
    while len(pq) != 0:
        vdist, v = pq.pop()

        # Loop over neighbouring nodes.
        for end, cost in graph[v]:
            # Work out the distance from the start, via this node's
            # shortest path, to the neighbouring node.
            newdist = vdist + cost
            if not visited[end]:
                # If we haven't seen the neighbour yet, queue it.
                pq.insert(newdist, end)
                parents[end] = v
                distances[end] = newdist
                visited[end] = 1
            elif newdist < distances[end]:
                # If we've seen it, and it's closer, decrease its distance.
                pq[end] = newdist
                parents[end] = v
                distances[end] = newdist

    return parents

# The shortest path from one node to another.
def shortest_path(graph, start, end):
    paths = all_shortest_paths(graph, start)
    nodes = [end]
    next = end
    while next != start:
        next = paths[next]
        nodes.append(next)
    nodes.reverse()
    return nodes

if __name__ == '__main__':
    # How to get from A to B.
    print shortest_path(data, 'a', 'b')
----------------------------------------------------------------------

-- 
	 Carey Evans  http://home.clear.net.nz/pages/c.evans/
More information about the Python-list mailing list