Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Shortest path algorithm (other than Dijkstra)

Reply
Thread Tools

Shortest path algorithm (other than Dijkstra)

 
 
ThanhVu Nguyen
Guest
Posts: n/a
 
      08-22-2004
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,
 
Reply With Quote
 
 
 
 
ThanhVu Nguyen
Guest
Posts: n/a
 
      08-22-2004
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,


 
Reply With Quote
 
 
 
 
nl
Guest
Posts: n/a
 
      08-22-2004
> 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


 
Reply With Quote
 
rossum
Guest
Posts: n/a
 
      08-22-2004
On Sat, 21 Aug 2004 22:01:31 -0400, ThanhVu Nguyen
<(E-Mail Removed)> 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
 
Reply With Quote
 
Carter Smith
Guest
Posts: n/a
 
      08-24-2004
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" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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,



 
Reply With Quote
 
Paul
Guest
Posts: n/a
 
      08-24-2004
"Carter Smith" <(E-Mail Removed)> 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" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
> > 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.
 
Reply With Quote
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      08-24-2004
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
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
libboost, python, and dijkstra shortest path Bytter Python 2 11-29-2006 08:14 PM
shortest mean path length diffuser78@gmail.com Python 0 10-06-2006 08:51 PM
Qquestion on Shortest paths algorithm costantinos@gmail.com C++ 5 07-27-2006 09:23 PM
Average All-Pair Shortest Path on a Graph Adam Hartshorne C++ 1 01-23-2006 04:32 PM
Recursive algoritme for finding the shortest path Webdad C++ 20 12-09-2004 06:51 PM



Advertisments