Какая реализация какого алгоритма поиска пути будет самой быстрой в моем сценарии?
Я ищу алгоритм поиска пути, который позволит мне найти кратчайший маршрут между известными точками A и B, которые являются узлами, и те, которые связаны с другими узлами.
В моем случае существует около 20000 узлов, каждый из которых может иметь до 16 подключений (ссылок), которые направлены (под этим я подразумеваю, если узел A подключен к узлу B, это не означает, что узел B подключен к узел А, это для правостороннего движения и левостороннего движения, для автомагистралей)
Чтобы избежать проблем, вот изображение того, что я имею в виду со связями (наряду с направленными):
Пример карты:
От A до D самый короткий путь здесь будет A-> C-> D, а от D до A это будет просто D-> A
Я знаю, что все расстояния между каждой связью и никакие расстояния не являются отрицательными.
(Потому что я знаю все позиции XYZ моих узлов)
Короче:
-Какой самый быстрый алгоритм в C или C ++ (я могу использовать оба) для моего случая?
-Конечно, мне нужно получить маршрут, но мне также нужно (рассчитать / или) получить расстояние от точки A до точки B)
-Есть ли библиотека для моих нужд?
-По желанию: есть ли библиотека с многопоточностью (поддержка) для этого (если да, то какая)?
-Есть ли примеры кода?
Я задаю этот вопрос потому, что хочу улучшить код, который работает очень медленно. Я хочу сделать это, переписав код, потому что в настоящее время Dijkstra используется, а не мент для этой ситуации.
Код, который я сейчас использую, находится здесь:
https://gpb.googlecode.com/files/RouteConnector_180.zip
Также вот пример использования в реальной жизни кода:
Решение
Пытаться Алгоритм Дейкстры. Также Повысьте :: Graph имеет реализованы Это.
Другие решения
Доказано, что * является самым быстрым алгоритмом поиска пути для общей проблемы.