Как обрабатывать (используя любые алгоритмы, такие как BFS и т. Д.) Большой график? [Дубликат]

Внутренние две петли Флойда-Варшалла - это, по сути, матричное умножение с добавлением, замененным на min, и умножение заменяется на сложение. Вы можете делать умножение матрицы с помощью map-reduce, поэтому вы можете реализовать Floyd Warshall с | V | map-reduce.

На странице wikipedia на Floyd-Warshall:

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

Внутренние две петли (i и j, строки с 7 по 11) структурно то же самое, что и матричное умножение, и вы можете адаптировать любое решение «матричное умножение на карте» для выполнения этого.

Внешний цикл (k) становится | V | Карта-уменьшает.

Я хотел бы предложить следующий подход - для нахождения кратчайших путей в графе с помощью map-reduce.

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

Представьте, что информация о графике хранится в виде списков смежности (с полезной нагрузкой, представляющей пути между соответствующими узлами). Например:

A -> [ {B, "A-B"}, {C, "A-C"}, {D, "A-D"} ]

Из приведенного примера - мы можем «вывести» информацию о следующих соединениях в графике:

1) Прямые соединения

• A -> B (путь: "A-B")
• A -> C (путь: "A-C")
• A -> D (путь: "A-D" ])

2) Транзитивные соединения через узел A

• B -> C (путь: "B-A-C") (где path("B -> C") == reverse(path("A -> B")) + path("A -> C"))
• C -> B (путь: "C-A-B")
• C -> D (путь: "C-A-D")
• D -> C (путь: "D-A-C")
• D -> B (путь: "D-A-B")
• B -> D (путь: "B-A-D")

Другими словами: мы просто «отображает» одну запись списка смежности - нескольким парам доступных друг другу узлов (для всех сгенерированных пар - существует путь).

Каждая пара узлов фактически представляет собой соединение: Source -> Target.

Итак, теперь мы можем объединить все пары, которые имеют один и тот же исходный узел:

Source -> [{Target 1, "Path-to-Target-1"}, {Target 2, "Path-to-target-2"}, ...]

Собственно, после комбинации - каждый источник будет связанный со списком целевых узлов: список может содержать дублированные целевые узлы ( дублированные целевые узлы, просто соответствуют различным возможным путям).

Итак, нам просто нужно удалить дубликаты из списка целевых узлов (чтобы сохранить только те целевые узлы, которые соответствуют самым коротким путям).

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

Итак, наконец - просто повторите эти шаги уменьшения карты до сходимости.