Нахождение всех кратчайших путей от каждой пары узлов на графике
Я имею о 70k узлах и 250k краях, и график не обязательно соединен. Очевидно, использование эффективного алгоритма крайне важно.Что Вы порекомендуете?
Как примечание стороны, я ценил бы совет относительно того, как разделить задачу между несколькими машинами - который даже возможен с этим видом проблемы?
Спасибо
4 ответа
Вы можете использовать алгоритм Флойда-Уоршалла . Это решает именно эту проблему.
Сложность - O (V ^ 3).
Существует также алгоритм Джонсона со сложностью O (V ^ 2 * log V + VE). Последний также легко распространять, потому что он запускает алгоритм Дейкстры V раз, что можно делать параллельно.
Есть два наивных способа распараллелить эту проблему:
1) Определить подкомпоненты и распределить их по разным компьютерам. Длина пути между двумя узлами от двух разных компонентов не определена.
2) Загрузите граф на разные компьютеры и дайте каждому компьютеру список узлов для вычисления всех кратчайших путей. Результаты для одного узла не зависят от результатов для другого узла, поэтому вы можете распараллелить эту проблему.
Плюс: не так сложно реализовать, но я бы сделал это так, только если вам нужно решить эту проблему один раз. Если это повторяющаяся проблема, возможно, вам стоит взглянуть на распределенный алгоритм.
Используйте igraph , он написан на C, довольно быстро, и вы можете использовать Python в качестве языка-оболочки.
Посмотрите статьи / публикации, в которых есть следующие ключевые слова: алгоритмы поиска по распределенному графу. Вот , который может помочь.
Также есть этот документ, содержащий только учетную запись ACM: Распределенные вычисления на графах: алгоритмы кратчайшего пути
MapReduce - отличный распределенный алгоритм для этого, хотя он может быть слишком мощным. Если вас это интересует, посмотрите эту лекцию или, может быть, эту запись в блоге для вдохновения. (Фактически, когда меня учили MapReduce, это был один из первых примеров.)
Для 250 тыс. Ребер и 70 тыс. Граф кажется относительно разреженным, алгоритм Дейкстры работает в O (E + V log V) для каждого узла для полного времени работы (все источники) O (VE + V ^ 2 log V) . Это должно быть достаточно быстро, но для Дейкстры действуют обычные предостережения. (Отрицательные ребра.)
Вы также можете взглянуть на алгоритм Джонсона , если ваша задача имеет дело с отрицательными весами, но не с отрицательными циклами. В частности, он также может быть распределен, поскольку он берет взвешенный граф и запускает алгоритм Дейкстры из каждого узла.