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

Question

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

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

Answer 1

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

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

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

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

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

Answer 2

Вы также можете попытаться дать A * алгоритм вращение.

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