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

Recipe 578156 revision 2 

import heapq as hq
inf = float('Inf')

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

    Q = [(0, s)]
    hq.heapify(Q)

    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)

Diff to Previous Revision

--- revision 1 2012-06-06 00:33:32
+++ revision 2 2012-06-06 00:34:13
@@ -7,7 +7,7 @@
     Q = [(0, s)]
     hq.heapify(Q)
 
-    d = [float('Inf') for i in range(n)]
+    d = [inf for i in range(n)]
     d[s]=0

History