473,320 Members | 2,161 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

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,
Jul 22 '05 #1
6 5859
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,
Jul 22 '05 #2
nl
> 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
Jul 22 '05 #3
On Sat, 21 Aug 2004 22:01:31 -0400, ThanhVu Nguyen
<ng************@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,


Google is your friend:

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

rossum

--

The ultimate truth is that there is no Ultimate Truth
Jul 22 '05 #4
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" <ng************@yahoo.com> wrote in message
news:u7********************@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,

Jul 22 '05 #5
"Carter Smith" <ne**@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" <ng************@yahoo.com> wrote in message
news:u7********************@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.
Jul 22 '05 #6
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
kb******@gascad.at
Jul 22 '05 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
by: Lau | last post by:
How do I easily calculate the shortest path between two geographical spots on a map? The map is divided into zones. So I guess it is possible to use Dijkstra’s Shortest Path algorithm, but it...
20
by: Webdad | last post by:
Hi! I running my first year as industrial engineer (informatics) We have an assignment to do : .... create a playfield (matrix). Some places in that field are blocked, so you can't pass them....
5
by: leezard | last post by:
I am developing a program using VB.NET that will accept a start and end point, the system then will generate the shortest path to reach the end point. Anyone here have idea on doing this or some...
4
by: Shuch | last post by:
Hi all, I am in shortage of time...and i want to know if someone has a code written in c++ or c for finding the shortest path using stack or queue??????my specifications r as follow: Input...
5
by: costantinos | last post by:
Hello. I have implemented the Dijkstra shortest path algorithm, it works fine but I have one question on how I can improve something. I want to find all the possible shortest paths from a node...
2
by: Bytter | last post by:
Hi everyone, I need to implement a very quick (performance-wise) Dijkstra shortest path in python, and found that libboost already has such thing. Problem is: I cannot find the installation...
0
by: Hugo Ferreira | last post by:
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: class PathFind(object):...
1
Ganon11
by: Ganon11 | last post by:
Hey guys, I'm back, and with another FUN question! My latest homework asks this question: "Suppose all the edge weights in a graph are integers between 1 and |E|. How fast can Dijkstra's...
1
by: Glenton | last post by:
Hi All Here is a very simple little class for finding a shortest route on a network, following Dijkstra's Algorithm: #!/usr/bin/env python #This is meant to solve a maze with Dijkstra's...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.