finding shortest path between two points

[Stephen Woodbridge]

Solomon,

Dijkstra's algorithm works with nodes and arcs, arcs are connections
between nodes and each arc has a cost associated with traversing it. The
cost is can be anything you want it to be or a combined cost. For
example, the distance is the cost if you are interested in "shortest
distance", time = distance / avg. speed can be the cost if you want to
compute shortest time. On a Toll road you can equate $/mile to a fake
time or distance penalty to avoid or take into account tolls, etc.

So you will need to first get the Dijkstra's code working with just test
data and then you will need to populated the data structure out of your
database before each run. Since the network does not change between
runs, you might be able to extract the whole network into a temporary
structure and then just extract the costs before each run because this
is what is changing.

The link below has pseudo code and you can search for actual C/C++
implementations on the web.

-Steve

thuo solomon wrote:
> thanks a lot for your guidance. I had this idea about Dijkstra's but i
> didn't know where to start. I am coding campus project where i have to
> implement some pathfinding. now i was wondering whether i can get some
> more directions from u. the data is in the database, the weights of the
> different road sections keeps on changing as traffic conditions changes.
> since u've arleady implemented this, can get some pseudo code for this.
> i'll appreciate very much
> regards solomon
>
> */Stephen Woodbridge <woodbri at swoodbridge.com>/* wrote:
>
>     That would be Dijkstra's algorithm, see:
>
>     http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html
>
>     There are lots of examples of code on the net for this. I have
>     implemented a prototype, but it is not opensource. You can play with
>     the
>     demo I have at
>
>     http://imaptools.com/demos1/?tab=2
>
>     -Steve
>
>     Solomon wrote:
>      > 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.
>      >
>
>
>
> *"Dr solomon"*
>
> __________________________________________________
> Do You Yahoo!?
> Tired of spam? Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com
>