|
![](/i/fill.gif) |
> As far as I can tell, Dijkstra's algorithm appears to visit *all* the
> nodes of the graph. You can then read off the optimal path from the
> initial node to any desired node - but surely computing the distance
> function for every road in the country would be infeasible?
>
> I guess if you know "approximately" what the optimal distance ought to be,
> you can just ignore any node that's further away then that or something...
> You're still computing quite a lot of data though.
You're beginning to invent the A* algorithm there ;-)
http://en.wikipedia.org/wiki/A*
I assume in real life applications there is some custom algorithm with many
additions and hacks based on knowledge of the road system (as opposed to
applying this to say a computer network). Also I assume that roads are
classified into speed ratings, so first it checks for any nearby motorways
at either end and then checks a route based on that, before fiddling with
the end sections etc, I imagine it can be quite complex!
Post a reply to this message
|
![](/i/fill.gif) |