finding shortest path between two points

[Mike Juvrud]

Deijkstra is fine for a relatively limited number of arcs. However, once
you start solving a graph with more than a couple thousand arcs you can
hit a serious wall and solutions can take minutes...especially if you
are attempting to span the breadth of the graph.

You may want to look into the A* (A star) algorithm for more efficient
solutions on large graphs.

I wrote an implementation of the deijkstra algorithm in Perl for use in
MapServer. Unfortunately I can't provide the code as it may become part
of a larger project, but I can help answer questions.

Here are some links I found useful for the A star algorithm:
http://theory.stanford.edu/~amitp/GameProgramming/
http://www.avglab.com/andrew/soft.html
http://jung.sourceforge.net/
http://www.policyalmanac.org/games/aStarTutorial.htm
http://www.codeproject.com/csharp/graphs_astar.asp?df=100&forumid=15953&
exp=0&select=537200
http://palantir.swarthmore.edu/maxwell/classes/e28/S00/reports/groom-joh
nson-nelson-olshfski-lab2/

It's been a good 6-months since I worked on these algorithms, but I'll
try to answer your questions about either.

*******************
Mike Juvrud
GIS Programmer
Glenwood, MN USA
320.634.4410
www.mudlabs.com
mike at mudlabs.com
*******************
------------------------------

Date:    Fri, 4 Mar 2005 11:06:10 -0600
From:    Solomon <solo6259 at YAHOO.COM>
Subject: finding shortest path between two points

hi guys
 thank u for ur support. now does anyone has a clue on how to implement
pathfinding. the user specifies source and destination, and code finds
the shortest distance between source and destination (like what is
implemeted in yahoo maps) and then the path is highlighted. am using
mapserver 4.4.2,phpmapscript,oracle 9i spatial all running on linux. any
help in the right direction will be appreciated.

------------------------------

--
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.308 / Virus Database: 266.6.2 - Release Date: 3/4/2005