Нахождение всех кратчайших путей из каждой пары узлов на графике

Question

У меня около 70 тыс. Узлов и 250 тыс. Ребер, и график не обязательно связан. Очевидно, что использование эффективного алгоритма имеет решающее значение. Что вы рекомендуете?

В качестве примечания, я был бы признателен за совет о том, как распределить задачу между несколькими машинами - возможно ли это даже при такой проблеме?

Спасибо

Answer 1

Вы можете использовать алгоритм Флойд-Варшалла . Это решает именно эту проблему.

Сложность O (V ^ 3).

Существует также алгоритм Джонсона со сложностью O (V ^ 2 * log V + VE). Последний также легко распространять, потому что он запускает алгоритм Дейкстры V раз, что можно сделать параллельно.

Answer 2

MapReduce - отличный распределенный алгоритм для этого, хотя он может быть слишком мощным. Если вам это интересно, посмотрите на эту лекцию или, может быть, на эту запись в блоге для вдохновения. (На самом деле, когда меня учили MapReduce, это был один из первых примеров.)

Для 250 тыс. Ребер и 70 тыс. Кажется, что график относительно разрежен, Алгоритм Дейкстры работает в O( E + V log V ) для каждого узла, для полного времени работы (всех источников) O( VE + V^2 log V ). Это должно быть достаточно быстро, но обычные предостережения относятся к Дейкстре. (Отрицательные края.)

Вы также можете взглянуть на алгоритм Джонсона , если ваша проблема связана с отрицательными весами, но не с отрицательными циклами. В частности, он также может быть распределен, так как он берет переоцененный граф и запускает алгоритм Дейкстры из каждого узла.

Answer 3

Существует два наивных способа распараллеливания этой проблемы:
1) Определите подкомпоненты и распределите их по разным компьютерам. Длина пути между двумя узлами из двух разных компонентов не определена.

2) Загрузить график на разных компьютерах и дать каждому компьютеру список узлов для расчета всех кратчайших путей. Результаты для одного узла не зависят от результатов другого узла, поэтому вы можете распараллелить эту проблему.

Перевернутый: не слишком сложно для реализации, но я бы сделал это только так, если вам придется решить это один раз. Если это повторяющаяся проблема, вы можете посмотреть на распределенный алгоритм.

Используйте igraph , он написан на C, довольно быстро, и вы можете использовать Python в качестве языка оболочки

Answer 4

Посмотрите статьи / публикации, которые имеют следующие ключевые слова: алгоритмы поиска по распределенным графам. Здесь может помочь.

Также есть бумага только для этой учетной записи ACM: Распределенные вычисления на графиках: алгоритмы кратчайшего пути