Hi all,
I have been going through the Dijkstra algorithm in
the hope of putting a very basic route finding program
together.
I'd like to run through what I believe the algorithm
uses to determine the route and see whether or not
anyone out there can correct me or confirm I'm in the
right ball-park:
1. Origin and Destination nodes are set (in MI they'll
be coordinate pairs?)
2. each node is given a weighting factor to show it's
relationship to the destination node (my
interpretation is the weighting is a distance value
(straight line) to the destination and the general
goal is to continue along a path where the weighting
value decreases until you get to the destination)
3. As the route algorithm searches each node, each
node whose weighting is lower than the previous node
is sought after as it means it's closing in on the
destination.
4. Then repeats until weighting node is the
destination node
Is this an accurate approach to the algorithm?? If so,
how does one stop the route finder from jumping nodes
from one street to another??
I was thinking of creating a grid over the roads where
the origin and destination exists. marking the grids
where they intersected with any road. Then weighted
each grid with the distance to the destination and
then ensured that the algorithm moved from/to adjacent
squares until destination reached. Problem is, this
won't work for roads that move AWAY from the
destination but still get there.
Regards
Ben Crane
__________________________________
Do you Yahoo!?
Yahoo! Small Business - Try our new resources site!
http://smallbusiness.yahoo.com/resources/
---------------------------------------------------------------------
List hosting provided by Directions Magazine | www.directionsmag.com |
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
Message number: 16032
