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