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 ```

Rob Malo 12 years, 4 months ago

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, 4 months ago

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)

### Required Modules

• (none specified)