dijkstra.py

   1 #!/usr/bin/python
   2 # -*- encoding: utf-8 -*-
   3
   4 import heapq as hq
   5 inf = float('Inf')
   6
   7 def dijkstra(G, s):
   8     n = len(G)
   9
  10     Q = [(0, s)]
  11
  12     d = [inf for i in range(n)]
  13     d[s]=0
  14
  15
  16     while len(Q)!=0:
  17         (cost, u) = hq.heappop(Q)
  18
  19         for v in range(n):
  20             if d[v] > d[u] + G[u][v]:
  21                 d[v] = d[u] + G[u][v]
  22                 hq.heappush(Q, (d[v], v))
  23
  24     return d