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, 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,
> 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
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
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,
"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.
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
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...
|
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....
|
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...
|
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...
|
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...
|
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...
|
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):...
|
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...
|
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...
|
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...
|
by: ryjfgjl |
last post by:
ExcelToDatabase: batch import excel into database automatically...
|
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...
|
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...
|
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...
|
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)...
|
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...
|
by: Defcon1945 |
last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
|
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...
| |