Shortest path algorithm (other than Dijkstra)

Discussion in 'C++' started by ThanhVu Nguyen, Aug 22, 2004.

  1. Hi all,

    I need recommendation for a very fast shortest path algorithm. The
    edges are all directed, positive weights. Dijkstra shortest path will
    solve it just fine but the if the graph is not parse then it takes about
    O(N^2) where N is the # of vertices, too much for large graphs.
    Furthermore, I don't need to know the all the path from a start point to
    every other single vertex as Dijkstra would provide. Just the shortest
    path from a start point to a defined end point.

    What other algorithms I can use ? Thanks in advance,
     
    ThanhVu Nguyen, Aug 22, 2004
    #1
    1. Advertising

  2. ThanhVu Nguyen wrote:
    > Hi all,
    >
    > I need recommendation for a very fast shortest path algorithm. The
    > edges are all directed, positive weights. Dijkstra shortest path will
    > solve it just fine but the if the graph is not parse then it takes about
    > O(N^2) where N is the # of vertices, too much for large graphs.
    > Furthermore, I don't need to know the all the path from a start point to
    > every other single vertex as Dijkstra would provide. Just the shortest
    > path from a start point to a defined end point.
    >
    > What other algorithms I can use ? Thanks in advance,



    What if I allow approximation shortest path , other than A* , any other
    known approx shortest path algorithm ? Thanks,
     
    ThanhVu Nguyen, Aug 22, 2004
    #2
    1. Advertising

  3. ThanhVu Nguyen

    nl Guest

    > What if I allow approximation shortest path , other than A* , any other
    > known approx shortest path algorithm ? Thanks,
    >


    Try googling on Depth First Search and/or Breadth First Search
     
    nl, Aug 22, 2004
    #3
  4. ThanhVu Nguyen

    rossum Guest

    On Sat, 21 Aug 2004 22:01:31 -0400, ThanhVu Nguyen
    <> wrote:

    >Hi all,
    >
    >I need recommendation for a very fast shortest path algorithm. The
    >edges are all directed, positive weights. Dijkstra shortest path will
    >solve it just fine but the if the graph is not parse then it takes about
    >O(N^2) where N is the # of vertices, too much for large graphs.
    >Furthermore, I don't need to know the all the path from a start point to
    >every other single vertex as Dijkstra would provide. Just the shortest
    >path from a start point to a defined end point.
    >
    >What other algorithms I can use ? Thanks in advance,


    Google is your friend:

    http://www.nist.gov/dads/HTML/shortestpath.html

    rossum



    --

    The ultimate truth is that there is no Ultimate Truth
     
    rossum, Aug 23, 2004
    #4
  5. ThanhVu Nguyen

    Carter Smith Guest

    A* can traverse 16km of 10m terrain data (real stuff like Idaho) in less
    than 2 one hundredths of a second on a 3.0Ghz system even with doing post
    processing to clean up the path (A* doesn't like large distances
    apparently). After solving the problem I found a similar (probably faster)
    solution in Game Programming Gems.

    It's a very fast algorithm if you have a more advanced knowledge of linked
    lists.

    Ben Kucenski
    www.icarusindie.com



    "ThanhVu Nguyen" <> wrote in message
    news:...
    > Hi all,
    >
    > I need recommendation for a very fast shortest path algorithm. The
    > edges are all directed, positive weights. Dijkstra shortest path will
    > solve it just fine but the if the graph is not parse then it takes about
    > O(N^2) where N is the # of vertices, too much for large graphs.
    > Furthermore, I don't need to know the all the path from a start point to
    > every other single vertex as Dijkstra would provide. Just the shortest
    > path from a start point to a defined end point.
    >
    > What other algorithms I can use ? Thanks in advance,
     
    Carter Smith, Aug 24, 2004
    #5
  6. ThanhVu Nguyen

    Paul Guest

    "Carter Smith" <> wrote in message news:<6KzWc.16709$L94.6861@fed1read07>...
    > A* can traverse 16km of 10m terrain data (real stuff like Idaho) in less
    > than 2 one hundredths of a second on a 3.0Ghz system even with doing post
    > processing to clean up the path (A* doesn't like large distances
    > apparently). After solving the problem I found a similar (probably faster)
    > solution in Game Programming Gems.
    >
    > It's a very fast algorithm if you have a more advanced knowledge of linked
    > lists.
    >
    > Ben Kucenski
    > www.icarusindie.com
    >
    >
    >
    > "ThanhVu Nguyen" <> wrote in message
    > news:...
    > > Hi all,
    > >
    > > I need recommendation for a very fast shortest path algorithm. The
    > > edges are all directed, positive weights. Dijkstra shortest path will
    > > solve it just fine but the if the graph is not parse then it takes about
    > > O(N^2) where N is the # of vertices, too much for large graphs.
    > > Furthermore, I don't need to know the all the path from a start point to
    > > every other single vertex as Dijkstra would provide. Just the shortest
    > > path from a start point to a defined end point.
    > >
    > > What other algorithms I can use ? Thanks in advance,


    take a look at Floyd's algorithm, its for m X n, so I can't compare
    the speed though.

    -Paul.
     
    Paul, Aug 24, 2004
    #6
  7. Paul wrote:
    >

    [snip]
    > > >
    > > > What other algorithms I can use ? Thanks in advance,

    >
    > take a look at Floyd's algorithm, its for m X n, so I can't compare
    > the speed though.
    >


    According to
    http://www.fearme.com/misc/alg/node88.html

    int floyds(int *matrix) {
    int k, i, j;

    for (k = 1; k <= n; k++)
    for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
    if (matrix[j] > (matrix[k] + matrix[k][j]))
    matrix[i,j] = matrix[k] + matrix[k][j];
    }

    where n is the number of nodes.
    Looks more like an O(n^3) algorithm to me.

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Aug 24, 2004
    #7
    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. Ricardo Batista

    dijkstra algorithm by object oriented

    Ricardo Batista, Nov 4, 2004, in forum: Python
    Replies:
    2
    Views:
    389
    Dave Benjamin
    Nov 5, 2004
  2. Ricardo Batista

    RE: dijkstra algorithm by object oriented

    Ricardo Batista, Nov 4, 2004, in forum: Python
    Replies:
    1
    Views:
    398
    Mike Meyer
    Nov 5, 2004
  3. Bytter
    Replies:
    2
    Views:
    501
    Roman Yakovenko
    Nov 29, 2006
  4. Hugo Ferreira

    Python Dijkstra Shortest Path

    Hugo Ferreira, May 16, 2007, in forum: Python
    Replies:
    0
    Views:
    924
    Hugo Ferreira
    May 16, 2007
  5. Gabriel Genellina

    Re: Python Dijkstra Shortest Path

    Gabriel Genellina, May 16, 2007, in forum: Python
    Replies:
    0
    Views:
    585
    Gabriel Genellina
    May 16, 2007
Loading...

Share This Page