Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Shortest path algorithm (other than Dijkstra) (http://www.velocityreviews.com/forums/t285152-shortest-path-algorithm-other-than-dijkstra.html)

 ThanhVu Nguyen 08-22-2004 02:01 AM

Shortest path algorithm (other than Dijkstra)

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 08-22-2004 03:04 AM

Re: Shortest path algorithm (other than Dijkstra)

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,

 nl 08-22-2004 09:05 AM

Re: Shortest path algorithm (other than Dijkstra)

> 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

 rossum 08-22-2004 11:11 PM

Re: Shortest path algorithm (other than Dijkstra)

On Sat, 21 Aug 2004 22:01:31 -0400, ThanhVu Nguyen
<nguyenthanhvuh@yahoo.com> 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,

rossum

--

The ultimate truth is that there is no Ultimate Truth

 Carter Smith 08-24-2004 04:45 AM

Re: Shortest path algorithm (other than Dijkstra)

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" <nguyenthanhvuh@yahoo.com> wrote in message
news:u7GdnRtQIMXmY7rcRVn-pA@comcast.com...
> 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,

 Paul 08-24-2004 11:14 AM

Re: Shortest path algorithm (other than Dijkstra)

"Carter Smith" <news@email.icarusindie.com> 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" <nguyenthanhvuh@yahoo.com> wrote in message
> news:u7GdnRtQIMXmY7rcRVn-pA@comcast.com...
> > 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.

 Karl Heinz Buchegger 08-24-2004 12:50 PM

Re: Shortest path algorithm (other than Dijkstra)

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[i][j] > (matrix[i][k] + matrix[k][j]))
matrix[i,j] = matrix[i][k] + matrix[k][j];
}

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

--
Karl Heinz Buchegger