Python Dijkstra Shortest Path

[Hugo Ferreira]

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:

class PathFind(object):
    def __init__(self):
        self.G = defaultdict(dict)
        self.E = defaultdict(dict)

    def addEdge(self, va, vb, cost, edge, way):
        if way == -1: (vb, va) = (va, vb)
        self.G[va][vb] = edge
        if not way: self.G[vb][va] = edge
        self.E[edge] = cost

    def findPath(self, start, end):
       def flatten(L):       # Flatten linked list of form [0,[1,[2,[]]]]
         while len(L) > 0:
           yield L[0]
           L = L[1]

       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, path)

             if v1 == end: return list(flatten(path))[::-1]

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

    def getEdges(self, path):
        edges = []
        for ix in xrange(len(path) - 1):
            edges.append(self.G[path[ix]][path[ix + 1]])
        return edges

addEdge() is used to initialize the Graph. It takes a way param: if -1
then the vertex order is reversed; 0 means it is bidir; 1 vertex order
is maintained.

This version maintains two Dictionaries: one for
pair_of_vertexes->edge and another for edge->cost.

findPath() will find the path between two vertexes and
getEdges(findPath()) will return this list of edges for that path.

The "Eliminate the dots" pattern actually improved performance in
about 10%. Still, I'm looking for some way to improve even more the
performance, while maintaining the dijkstra intact (I don't want an
A*). Psyco gave me about 20% of improvement. I wonder if anyone has
any idea to make this faster (maybe map? list comprehension? some
python trick?)...

Profiling blames the heapq (eheh). On a my CoreDuo T2300, it takes
1.6seconds to find a path of 800 vertexes in an half a million mesh.

Greetings!

Hugo Ferreira