Если бы нужно было закодировать цифровую карту, такую ​​как Google Maps, используя алгоритм Дейкстры, чтобы найти кратчайший путь, как узлы будут представлены / закодированы?

Question

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

Answer 1

Узлы и пути, по сути, неоднозначны и декларируют, что вы хотите, чтобы они представляли.Является ли узел пересечением?(масштабирование по размеру города) Является ли узел городом?(Масштабирование в масштабе провинции / штата, страны или континента).

Для путей также потребуется некоторый вес между ними.Итак, если вы выбираете пересечения для узлов, каков вес между узлами A и B и вес между узлами B и C?Я предполагаю, что вы захотите использовать время, но у вас нет таких данных, не так ли?

Есть больше проблем, чем просто узлы, я думаю ... без базы данных весов для запуска по короткому путиАлгоритм против вашей смерти в воде.

В более абстрактном виде вам нужно определить ваши узлы (точки, вероятно, используя координаты широты / долготы), а затем определить весовые коэффициенты между каждым узлом, которые могут бытьдостиг.Таким образом, снова используя идею ABC, может ли узел A напрямую добраться до узла C?Может ли он достичь этого через B?

      4       3
A ------- B--------
  \                \
   -----------------C
            8

A -> B = 4
B -> C = 3
A -> C = 8
A -> B -> C = 7