paths

   1 from Queue import PriorityQueue
   2 def dijkstra(start):
   3     back = list()
   4     cost = list()
   5     for i in range(len(E)):
   6         back.append(None)
   7         cost.append(None)
   8     q = PriorityQueue()
   9     q.put((0, start))
  10     while not q.empty():
  11         p = q.get()
  12         src = p[1]
  13         for e in E[src]:
  14             dst = e[0]
  15             c = p[0] + e[1]
  16             if cost[dst] is not None and cost[dst] <= c:
  17                 continue
  18             back[dst] = src
  19             cost[dst] = p[0] + e[1]
  20             q.put((cost[dst], dst))
  21     return (back, cost)
  22 def shortest_path(start, goal, back, cost):
  23     route = []
  24     p = goal
  25     while p != start:
  26         route.append(p)
  27         p = back[p]
  28     route.reverse()
  29     return route
  30 sys.argv[1:] = shortest_path(start, goal, *dijkstra(start))