443,890 Members | 1,226 Online Need help? Post your question and get tips & solutions from a community of 443,890 IT Pros & Developers. It's quick & easy.

# Shortest path algorithm (other than Dijkstra)

 P: n/a 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 Replies

 P: n/a 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

 P: n/a > 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

 P: n/a On Sat, 21 Aug 2004 22:01:31 -0400, ThanhVu Nguyen wrote: Hi all,I need recommendation for a very fast shortest path algorithm. Theedges are all directed, positive weights. Dijkstra shortest path willsolve it just fine but the if the graph is not parse then it takes aboutO(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 toevery other single vertex as Dijkstra would provide. Just the shortestpath 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

 P: n/a 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: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

 P: n/a "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: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

 P: n/a 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 discussion thread is closed

Replies have been disabled for this discussion. 