Re: Python Dijkstra Shortest Path

Discussion in 'Python' started by Gabriel Genellina, May 16, 2007.

  1. En Wed, 16 May 2007 00:39:20 -0300, Hugo Ferreira <>
    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
     
    Gabriel Genellina, May 16, 2007
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ThanhVu Nguyen
    Replies:
    6
    Views:
    5,846
    Karl Heinz Buchegger
    Aug 24, 2004
  2. Webdad
    Replies:
    20
    Views:
    1,945
    Jochus
    Dec 9, 2004
  3. Replies:
    0
    Views:
    369
  4. Bytter
    Replies:
    2
    Views:
    513
    Roman Yakovenko
    Nov 29, 2006
  5. Hugo Ferreira

    Python Dijkstra Shortest Path

    Hugo Ferreira, May 16, 2007, in forum: Python
    Replies:
    0
    Views:
    935
    Hugo Ferreira
    May 16, 2007
Loading...

Share This Page