Welcome, guest | Sign In | My Account | Store | Cart

Dijkstra shortest path algorithm.

Python, 113 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
# Dijkstra Shortest Path Algorithm
# http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
# FB - 201110296
from heapq import heappush, heappop # for priority queue
pq = []

class node:
    label = ''
    # adjacency list of the node 
    neighbors = [] # list of nodes
    distances = [] # distances to neighbors
    # for Dijkstra
    prevNode = None
    totalDistance = float('Inf')
    visited = False
    # constructor
    def __init__(self, label):
        self.label = label
        self.neighbors = []
        self.distances = []
        self.prevNode = None
        self.totalDistance = float('Inf')
        self.visited = False


# find the shortest paths to all nodes recursively
def dijkstra(node):
    # visit all neighbors and update them if necessary
    for i in range(len(node.neighbors)):
        n = node.neighbors[i]
        d = node.distances[i]
        if n.totalDistance > d + node.totalDistance:
            n.prevNode = node
            n.totalDistance = d + node.totalDistance
            heappush(pq, (n.totalDistance, n))
    node.visited = True

    (d, ne) = heappop(pq)
    if not ne.visited:
        dijkstra(ne)

# get the shortest path to the given node
def route(endNode):
    node = endNode
    labels = [endNode.label]
    # distances = []
    while node.label != node.prevNode.label:
        # distances.append(node.totalDistance - node.prevNode.totalDistance)
        node = node.prevNode
        labels.append(node.label)
    labels.reverse()
    return labels
    # distances.reverse()
    # return (labels, distances)
        
# create a graph
a = node('a')
b = node('b')
c = node('c')
d = node('d')
e = node('e')
f = node('f')
graph = (a, b, c, d, e, f)

# create bidirectional edges of the graph
edges = []
edges.append((b, c, 3))
edges.append((d, e, 1))
edges.append((b, d, 2))
edges.append((c, e, 1))
edges.append((a, b, 1))
edges.append((a, d, 1))
edges.append((c, f, 1))
edges.append((e, f, 3))

# create adjaceny list of neighbors for each node
for edge in edges:
    edge[0].neighbors.append(edge[1])
    edge[0].distances.append(edge[2])
    edge[1].neighbors.append(edge[0])
    edge[1].distances.append(edge[2])

# print the graph
print 'The graph:'
print
for n in graph:
    print 'Node: ', n.label
    print 'Neighbors:'
    for i in range(len(n.neighbors)):
        print n.neighbors[i].label, n.distances[i]
    print

# find the shortest paths to all neighbors starting w/ the given node
startNode = a
print 'Route start node:', startNode.label
startNode.prevNode = startNode
startNode.totalDistance = 0
dijkstra(startNode)

##print
##print 'The graph after Dijkstra:'
##print
##for n in graph:
##    print 'Node:', n.label
##    print 'totalDistance:', n.totalDistance
##    print 'prevNode:', n.prevNode.label
##    print

# print the shortest path to the given node
endNode = f
print 'Route end node:', endNode.label
print 'Route:', route(endNode)
print 'Total distance:', endNode.totalDistance

2 comments

Rob Malo 12 years, 5 months ago  # | flag

Something is flawed in the code. At least if I understand it correctly.

As an example, if you replace lines 56-64 with:

edges.append((b, c, 3))
edges.append((d, e, 1))
edges.append((b, d, 2))
edges.append((c, e, 1))
edges.append((a, b, 1))
edges.append((a, d, 1))
edges.append((c, f, 1))
edges.append((e, f, 3))

The output of the code is:

Route start node: a 
Route end node: f
Route: ['a', 'b', 'c', 'f']
Total distance: 5

Clearly the shortest route is: ['a','d','e','c','f'] with total distance:4

I'm not sure if there is an elegant fix to this problem. It seems that once the code uses an edge and saves a total distance to that node, it does not have the ability to adjust the total distance if the total distance to the previous node decreases.

FB36 (author) 12 years, 5 months ago  # | flag

Thanks for letting me know. I changed the algorithm to use a priority queue. Now it outputs the correct route (it is not exactly same w/ your answer but still correct):

Route start node: a

Route end node: f

Route: ['a', 'd', 'e', 'c', 'f']

Total distance: 4

Created by FB36 on Mon, 20 Dec 2010 (MIT)
Python recipes (4591)
FB36's recipes (148)

Required Modules

  • (none specified)

Other Information and Tasks