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

Dijkstra(G,s) finds all shortest paths from s to each other vertex in the graph, and shortestPath(G,s,t) uses Dijkstra to find the shortest path from s to t. Uses the priorityDictionary data structure (Recipe 117228) to keep track of estimated distances to each vertex.

Python, 87 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``` ```# Dijkstra's algorithm for shortest paths # David Eppstein, UC Irvine, 4 April 2002 # http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228 from priodict import priorityDictionary def Dijkstra(G,start,end=None): """ Find shortest paths from the start vertex to all vertices nearer than or equal to the end. The input graph G is assumed to have the following representation: A vertex can be any object that can be used as an index into a dictionary. G is a dictionary, indexed by vertices. For any vertex v, G[v] is itself a dictionary, indexed by the neighbors of v. For any edge v->w, G[v][w] is the length of the edge. This is related to the representation in where Guido van Rossum suggests representing graphs as dictionaries mapping vertices to lists of neighbors, however dictionaries of edges have many advantages over lists: they can store extra information (here, the lengths), they support fast existence tests, and they allow easy modification of the graph by edge insertion and removal. Such modifications are not needed here but are important in other graph algorithms. Since dictionaries obey iterator protocol, a graph represented as described here could be handed without modification to an algorithm using Guido's representation. Of course, G and G[v] need not be Python dict objects; they can be any other object that obeys dict protocol, for instance a wrapper in which vertices are URLs and a call to G[v] loads the web page and finds its links. The output is a pair (D,P) where D[v] is the distance from start to v and P[v] is the predecessor of v along the shortest path from s to v. Dijkstra's algorithm is only guaranteed to work correctly when all edge lengths are positive. This code does not verify this property for all edges (only the edges seen before the end vertex is reached), but will correctly compute shortest paths even for some graphs with negative edges, and will raise an exception if it discovers that a negative edge has caused it to make a mistake. """ D = {} # dictionary of final distances P = {} # dictionary of predecessors Q = priorityDictionary() # est.dist. of non-final vert. Q[start] = 0 for v in Q: D[v] = Q[v] if v == end: break for w in G[v]: vwLength = D[v] + G[v][w] if w in D: if vwLength < D[w]: raise ValueError, \ "Dijkstra: found better path to already-final vertex" elif w not in Q or vwLength < Q[w]: Q[w] = vwLength P[w] = v return (D,P) def shortestPath(G,start,end): """ Find a single shortest path from the given start vertex to the given end vertex. The input has the same conventions as Dijkstra(). The output is a list of the vertices in order along the shortest path. """ D,P = Dijkstra(G,start,end) Path = [] while 1: Path.append(end) if end == start: break end = P[end] Path.reverse() return Path ```

As an example of the input format, here is the graph from Cormen, Leiserson, and Rivest (Introduction to Algorithms, 1st edition), page 528:

<pre> G = {'s':{'u':10, 'x':5}, 'u':{'v':1, 'x':2}, 'v':{'y':4}, 'x':{'u':3, 'v':9, 'y':2}, 'y':{'s':7, 'v':6}} </pre>

The shortest path from s to v is ['s', 'x', 'u', 'v'] and has length 9.

Connelly Barnes 16 years, 9 months ago

Can be simplified (with tradeoffs in time and memory). Dijkstra's algorithm can be simplified by allowing a (cost, vertex)

pair to be present multiple times in the priority queue:

``````def shortest_path(G, start, end):
def flatten(L):       # Flatten linked list of form [0,[1,[2,[]]]]
while len(L) > 0:
yield L[0]
L = L[1]

q = [(0, start, ())]  # Heap of (cost, path_head, path_rest).
visited = set()       # Visited vertices.
while True:
(cost, v1, path) = heapq.heappop(q)
if v1 not in visited:
if v1 == end:
return list(flatten(path))[::-1] + [v1]
path = (v1, path)
for (v2, cost2) in G[v1].iteritems():
if v2 not in visited:
heapq.heappush(q, (cost + cost2, v2, path))
``````

If there are n vertices and m edges, the modified-Dijkstra algorithm

takes O(n+m) space and O(m*log(m)) time. In comparison, the Dijkstra

algorithm takes O(n) space and O((n+m)*log(n)) time. All time bounds

assume no hash collisions.

Using Eppstein's (excellent) dictionary graph representation, it takes O(n+m) space

to store a graph in memory, thus the memory overhead of the

modified-Dijkstra algorithm is reasonable.

I tested running times on a Pentium 3, and for complete graphs of ~2000

vertices, this modified Dijkstra function is several times slower than

Eppstein's function, and for sparse graphs with ~50000 vertices and

~50000*3 edges, the modified Dijkstra function is several times faster

than Eppstein's function.

P.S.: Eppstein has also implemented the modified algorithm in Python (see python-dev). This implementation is faster.

Ciamac Faridani 14 years, 4 months ago

GraphViz Output. I have prepared a little script to visualize the network in graphViz just insert the output file in Dot or in this webpage http://ashitani.jp/gv/

``````G = {'s':{'u':10, 'x':5},
'u':{'v':1, 'x':2},
'v':{'y':4},
'x':{'u':3, 'v':9, 'y':2},
'y':{'s':7, 'v':6}}

f = open('dotgraph.txt','w')
f.writelines('digraph G {\nnode [width=.3,height=.3,shape=octagon,style=filled,color=skyblue];\noverlap="false";\nrankdir="LR";\n')
f.writelines
for i in G:

for j in G[i]:
s= '      '+ i
s +=  ' -> ' +  j + ' [label="' + str(G[i][j]) + '"]'
s+=';\n'
f.writelines(s)

f.writelines('}')
f.close()
print "done!"
``````
Eoghan Murray 14 years, 3 months ago

Variable Naming. Would 'vwLength' be better named 'startwLength' or maybe even 'pathDistance'?

poromenos 11 years, 11 months ago

Thanks for the recipe, but I think it would be ten times more readable with names such as "graph", "estimated_distances", "final_distances", etc.

nolfonzo 11 years, 10 months ago

Thanks for posting this. I had a stab at an implementation on my blog: http://rebrained.com/?p=392

It's a little pedestrian compared to the examples above as it follows the algorithm fairly literally.

``````import sys
def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
"""Find the shortest path between start and end nodes in a graph"""
# we've found our end node, now find the path to it, and return
if start==end:
path=[]
while end != None:
path.append(end)
end=predecessors.get(end,None)
return distances[start], path[::-1]
# detect if it's the first time through, set current distance to zero
if not visited: distances[start]=0
# 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','b')

"""
Result:
(20, ['a', 'y', 'w', 'b'])
"""
``````
Chris Laffra 8 years, 9 months ago

I took the modified version from Connelly Barnes, made it a bit simpler (adding some extra cost for the path/list operations), and uploaded the code and visualization to http://pyalgoviz.appspot.com. It shows a nice step-by-step progression of the nodes being visited. My version of the algorithm:

``````def shortestPath(graph, start, end):
queue = [(0, start, [])]
seen = set()
while True:
(cost, v, path) = heapq.heappop(queue)
if v not in seen:
path = path + [v]
if v == end:
return cost, path
for (next, c) in graph[v].iteritems():
heapq.heappush(queue, (cost + c, next, path))
``````
cheng li 7 years, 1 month ago

Hi David, I test this code by:

graph_dict = { "s1":{"s1": 0, "s2": 2, "s10": 1, "s12": 4, "s5":3}, "s2":{"s1": 1, "s2": 0, "s10": 4, "s12": 2, "s5":2}, "s10":{"s1": 2, "s2": 1, "s10": 0, "s12":1, "s5":4}, "s12":{"s1": 3, "s2": 5, "s10": 2, "s12":0,"s5":1}, "s5":{"s1": 3, "s2": 5, "s10": 2, "s12":4,"s5":0}, }

the distance turns out correctly, but the path doesn't. I also use function shortestPath to calculate path between s1 and s12, the result shows below:

({'s12': 2, 's1': 0, 's10': 1, 's5': 3, 's2': 2}, {'s2': 's1', 's10': 's1', 's5': 's1', 's12': 's1'}) ['s1', 's12']

Actually, the best path is s1->s10->s12.

I wirte the dijkstra too, but I think its time complexity is too high. How to make it faster?

```python

``````def dijkstra(graph,src):
length = len(graph)
type_ = type(graph)
if type_ == list:
nodes = [i for i in xrange(length)]
elif type_ == dict:
nodes = [i for i in graph.keys()]

visited = [src]
path = {src:{src:[]}}
nodes.remove(src)
distance_graph = {src:0}
pre = next = src

while nodes:
distance = float('inf')
for v in visited:
for d in nodes:
new_dist = graph[src][v] + graph[v][d]
if new_dist < distance:
distance = new_dist
next = d
pre = v
graph[src][d] = new_dist

path[src][next] = [i for i in path[src][pre]]
path[src][next].append(next)

distance_graph[next] = distance

visited.append(next)
nodes.remove(next)

return distance_graph, path

if __name__ == '__main__':
graph_list = [   [0, 2, 1, 4, 5, 1],
[1, 0, 4, 2, 3, 4],
[2, 1, 0, 1, 2, 4],
[3, 5, 2, 0, 3, 3],
[2, 4, 3, 4, 0, 1],
[3, 4, 7, 3, 1, 0]]

graph_dict = {  "s1":{"s1": 0, "s2": 2, "s10": 1, "s12": 4, "s5":3},
"s2":{"s1": 1, "s2": 0, "s10": 4, "s12": 2, "s5":2},
"s10":{"s1": 2, "s2": 1, "s10": 0, "s12":1, "s5":4},
"s12":{"s1": 3, "s2": 5, "s10": 2, "s12":0,"s5":1},
"s5":{"s1": 3, "s2": 5, "s10": 2, "s12":4,"s5":0},
}

distance, path = dijkstra(graph_list, 2)
#print distance, '\n', path
distance, path = dijkstra(graph_dict, 's1')
print distance, '\n', path
``````

```

 Created by David Eppstein on Thu, 4 Apr 2002 (PSF)