Все пары кратчайших путей для неориентированного взвешенного разреженного графа
Каков наилучший алгоритм для нахождения всех пар кратчайших путей для неориентированного взвешенного разреженного графа? В частности, веса — это расстояния между узлами (и, следовательно, положительные). Обратите внимание, что мне нужны только длины пути (т.е. не сам путь). Мой график разрежен, поэтому он хранится в виде списка смежности.
Я нашел Дейкстру, Флойд-Варшалла, Джонсона и т. Д., Но ни один из них не подходит для моей цели. В случае Dijkstra вы запускаете версию с одним исходным кодом по всем вершинам, Floyd-Warshall предназначен для плотных графов, а Johnson — для направленных.
Я специально ищу реализацию в C ++.
Решение
Алгоритм Джонсона кажется наиболее подходящим для разреженных графов (если | V |> | E |, то сводится к O (V ^ 2logV), в отличие от O (V ^ 3) с FW). Однако, поскольку алгоритм Джонсона тратит первый шаг на то, чтобы сделать веса неотрицательными (которые вам не нужны), вы можете выполнить только второй шаг, как вы правильно указали, который по сути является просто Dijkstra из каждого узла. Это должно занять только O (VElogV), как указано здесь, на последнем слайде. Я не уверен, что смогу доказать, что это лучшее решение, но было бы лучшее (для нахождения кратчайших путей для неотрицательных весов) — я ожидал бы, что алгоритм Джонсонса будет использовать его после перезаписи весов.
Тот факт, что он работает с ориентированными графами, не должен вас беспокоить — вы можете конвертировать неориентированный граф в ориентированный просто путем преобразования каждого неориентированного ребра с двумя направленными ребрами, идущими назад и вперед (с простым временем O (E)). Это — если у вас нет ограничений по пространству.
Другие решения
Поскольку это неориентированный взвешенный разреженный график, он очень похож на дорожную сеть, поэтому я не думаю (из опыта), что существует лучший алгоритм, чем Дейкстра. Посмотрите на двунаправленную dijkstra, и, если у вас достаточно оперативной памяти, вы можете кэшировать деревья кратчайших путей (SPT) каждого узла, а затем просто выполнить «сопоставление» между SPT точки i и SPT точки j, где i! = к.
Я не проверял это, но эта статья 2013 года утверждает, что победила Дейкстру в 47 раз:
Ураков А. Р., Тимеряев Т. В .: ВСЕПАРНЫЕ КОРОТКИЕ ПУТИ АЛГОРИТМОВ ВЫСОКОРАЗМЕРНЫХ РАЗРЯДНЫХ ГРАФОВ:
Предложенный алгоритм ускоряет решение APSP в среднем в 47 раз быстрее по сравнению с алгоритмом Дейкстры. Для всех тестовых графиков алгоритм работает быстрее, чем алгоритм Дейкстры (минимальное ускорение в 34 раза быстрее). Во время испытаний степень вершин была увеличена до максимума 17. Это означает, что сложность удаления вершин увеличивается при разборке лишь незначительно.