Rod Engelsman wrote:
Does anybody know what the algorithm is that mapping programs like
Rand-McNally or Mapquest use to figure out the shortest route? I've been
curious about this for a while.
I imagine they're closely held trade secrets. The problem is
intrinsically hard (made more difficult when looking for the /fastest/
route, rather than the shortest), and requires both heuristics and a lot
of computing. Even on my 3.33GHz Pentium 4, it takes DeLorme Street
Atlas 2005 about a minute to calculate a door-to-door from my home in NJ
to my sister-in-law's in L.A. (about a 48-hour drive without breaks).
Google Earth took only about ten seconds, but I imagine the calculation
was done on a Google server. (DeLorme gave a somewhat shorter route, by
the way.)
--
John W. Kennedy
"...if you had to fall in love with someone who was evil, I can see why
it was her."
-- "Alias"
