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

Simple Dijkstra Algorithm (Python recipe) by Filippo Squillace
ActiveState Code (http://code.activestate.com/recipes/578156/)

The algorithm uses the priority queue version of Dijkstra and return the distance between the source node and the others nodes d(s,i).

Python, 32 lines
Download
 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
import heapq as hq
inf = float('Inf')

def dijkstra(G, s):
    n = len(G)

    Q = [(0, s)]

    d = [inf for i in range(n)]
    d[s]=0


    while len(Q)!=0:
        (cost, u) = hq.heappop(Q)

        for v in range(n):
            if d[v] > d[u] + G[u][v]:
                d[v] = d[u] + G[u][v]
                hq.heappush(Q, (d[v], v))

    return d




G = [\
        [0.0,  1.0,  3.0,  inf],\
        [1.0,  0.0,  1.0,  4.0],\
        [3.0,  1.0,  0.0,  2.0],\
        [inf,  4.0,  2.0,  0.0]]

d = dijkstra(G, 0)
Tags: graph