|
Posted by mensanator@aol.com on January 25, 2006, 8:29 pm
Please log in for more thread options jimirwin wrote:
>
> > I'm looking for some information about finding the shortest route for
> > routing on roads. I know what dykstra's algorithm is, and how it can
> > be used for this purpose, but i'm looking for information on how to
> > utilize it. Basically, what are the "inputs" and "outputs" of the
> > function? Do i need my roads as points and vectors/distance, or the
> > segments as coordinants? Is there any code that shows this, in c, c++
> > or even vb?
> >
> >
>
> For small road networks, Dijkstra's algorithm works OK. For large
> networks, you will likely have to create a hierarchical network of local
> roads, feeders, thoroughfares, and freeways. Otherwise, the astronomic
> number of potential routes slows the algorithm down dramatically, and you
> will compute the absolute shortest route, even it if means diverting off of
> interstates for short distances to save fractions of a mile or minutes.
> Most users would find that objectionable.
Like the directions you get from MapQuest.
I saw a set of such directions someone had printed. It was a
100 mile or so route. From the starting point, one was to head
west and north along various small state roads before eventually
intersecting US Route 12 and following it to the end.
Funny thing was US Route 12 is literally only 1 block north of the
starting point, so instead of mucking about on all those state roads
going west and north, the driver could have simply gone northwest
on the much larger US highway and probably saved an hour of
travel time.
>
> You can make the intersections the graph nodes, and the road segments
> between intersections as the graph edges. You can weight the edges by
> distance, estimated time, or whatever your creativity comes up with as a
> useful distance metric.
>
> --
> Jim Irwin
> http://www.holoscenes.com
| 
XML Sitemap