Как Google Maps и Nokia Maps генерируют маршруты из точки в точку

Question

Я хотел бы знать, есть ли у кого-нибудь идея относительно концепции создания двухточечного маршрута на картах Google и Nokia.Какая логика использовалась для определения маршрута и создания направлений из любой точки на карте в другую?Я не возражаю против догадок или чего-то в этом роде.Я просто хочу понять, как это работает.

Answer 1

Это всего лишь предположение, но, вероятно, что-то вроде алгоритм Дейкстры .Скорее всего, это какой-то алгоритм поиска в графе, где каждый узел представляет пересечение, а каждое ребро представляет участок улицы.

Answer 2

Я также добавлю, что график здесь, вероятно, также взвешен, причем каждый вес соответствует тому, насколько важна дорога.Например, автомагистрали между штатами могут иметь больший вес, чем государственные магистрали, которые имеют больший вес, чем местные дороги, которые имеют больший вес, чем простые улицы.Опционально, платные дороги могут иметь меньший вес, чем платные.