Python Dijkstra Shortest Path

[Gabriel Genellina]

En Wed, 16 May 2007 00:39:20 -0300, Hugo Ferreira <bytter at gmail.com>  
escribió:

> While trying to optimize this:
>
> http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466
>
> ... and still have a fast edge lookup, I've done the following tweaks:

I've replaced that strange deeply nested list with an old-fashioned tuple  
and got about a 10% improvement (over a small graph, 60 nodes). But you  
really should try the effect with larger objects.

     def findPath(self, start, end):
        q = [(0, start, ())]  # Heap of (cost, path_head, path_rest).
        visited = set()       # Visited vertices.

        # Eliminate the dots pattern
        push, pop, add = heapq.heappush, heapq.heappop, visited.add
        G, E = self.G, self.E

        while True:
           (cost, v1, path) = pop(q)
           if v1 not in visited:
              add(v1)
              path += (v1,)

              if v1 == end: return path

              for (v2, e) in G[v1].iteritems():
                  if v2 not in visited:
                    push(q, (cost + E[e], v2, path))

-- 
Gabriel Genellina