Кратчайший общий путь среди множества широты / долготы

Question

У меня есть набор из примерно 52 пар широта / долгота. Мне просто нужно найти кратчайший путь через все из них; не имеет значения, где находится начальная точка или конечная точка.

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

Вам известны какие-либо библиотеки или существующие скрипты / приложения, которые будут таким образом вычислять кратчайший путь? Код / библиотеки желательно использовать Python или Clojure, но это действительно не имеет значения.

Спасибо

Answer 1

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

Answer 2

В python лучшая библиотека для работы с графиками, которую я смог взять в руки, это networkx . Он поддерживает широкий спектр различных алгоритмов для поиска по короткому пути .

Перейти на это. Это действительно полный и хорошо продуманный.

Answer 3

Разве это не проблема коммивояжера , и поэтому нет эффективного способа ее решения?