Dijkstra's algorithm for shortest paths (Python recipe) by David Eppstein

ActiveState Code (http://code.activestate.com/recipes/119466/)

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:
         visited.add(v1)
         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.

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!"

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

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

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'])
        """

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]
            seen.add(v)
            if v == end:
                return cost, path
            for (next, c) in graph[v].iteritems():
                heapq.heappush(queue, (cost + c, next, path))

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

```