Оптимизация Дейкстры для плотного графа?

Question

Есть ли другой способ рассчитать кратчайший путь для близкого полного графика, кроме Dijkstra? У меня около 8000 узлов и около 18 миллионов ребер. Я прошел через нить "a to b on map" и решил использовать Дейкстра. Я написал свой скрипт в Perl, используя библиотеку Boost :: Graph. Но результат не тот, который я ожидал. Для вычисления одного кратчайшего пути понадобилось около 10 + минут, используя вызов $ graph-> dijkstra_shortest_path ($ start_node, $ end_node);

Я понимаю, что есть много краев, и это может быть причиной медленного времени работы. Я мертв в воде? Есть ли другой способ ускорить это?

Answer 1

Короткий ответ: Дикстра - ваша лучшая ставка, если вы хотите только несколько кратчайших путей, а алгоритм Флойда-Варшалла лучше, если вы хотите найти кратчайшие пути между каждой парой узлов.

• алгоритм Дейкстры находит кратчайшие пути от одного источника ко всем другим узлам в графе, для взвешенных графов. Он работает на плотных графах в O (V^2) времени.

• Floyd-Warshall находит кратчайшие пути между всеми парами узлов. Он требует плотного представления и работает в O (V^3) времени. Он работает на взвешенных или невзвешенных графиках.

Даже если ваш график плотно (в соответствии с названием вашего вопроса), что может быть какая-то польза для преобразования его в разреженный граф и используя редкую реализацию Дейкстры, если вы просто хотите, чтобы найти несколько кратчайшие пути. Пробежчики Dijkstra работают в O (E log V).

Обратите внимание, что это означает, что все ваши весы отрисовки неотрицательны; если они есть, то вы не можете использовать ни одно из них. Вам придется использовать еще более медленный алгоритм, например, Bellman-Ford.

Answer 2

Вы также можете попытаться дать A* algorithm a spin.

Этот подход особенно полезен, если у вас есть доступ к хорошей эвристике.