By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,922 Members | 1,689 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,922 IT Pros & Developers. It's quick & easy.

Python Dijkstra Shortest Path

P: n/a
While trying to optimize this:

.... 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:
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.


Hugo Ferreira
May 16 '07 #1
Share this question for a faster answer!
Share on Google+

This discussion thread is closed

Replies have been disabled for this discussion.