使用map reduce使用bfs遍历图的有效方法是什么

Question

这是一位招聘人员问我的面试问题，问题基本上是计算所有节点到每个节点的最短路径，我的解决方案是以下

启动所有可能的边缘（没有反向A-B与B-A相同）

每个节点将表示在下面（src，cost，current_list，dest）中，src和dest基本上是我们之前启动的所有可能的边

地图：

for each edge you traverse, you duplicate your tuple and add the current   
traversed node to the cost and current list. 
if the node is the destination you annotate finish, if the the node is 
in the current list, you annotate delete

减少：

Don't really need to do anything besides outputting finish and deleting 
delete and let the other node go through the next round of map
And by outputting I mean for each src, dest pair only output the least cost

招聘人员说这不高效，我可以看出这是如何不高效的，因为你是组合遍历的，但我能想到的唯一替代方案是，如果你有n个节点，那么生成n个服务器，并为每个节点执行dijkstra，招聘人员说，这也是错误的。有人能帮我解决这个问题吗？

编辑：

Ex。三角形图

边缘为A-B、B-C、C-A，路径成本为1

算法

1. 首先，我们启动所有可能的源-目的地对，记住边缘的反向不是唯一的A-B、A-C、B-C（省略B-A、C-A、B-C）

对于每个源-目的地对，我们有以下元组

(src=A, cost=None, current_list=A, dest=B, annotate=continue)
(src=A, cost=None, current_list=A, dest=C, annotate=continue)
(src=B, cost=None, current_list=B, dest=C, annotate=continue)

2. 现在我们开始地图缩减算法

   for each tuple in the tuple list we initiate:
       for each neighbor of the node at the end of current_list
           if the next neighbor is already in the current_list
               set annotate = delete
           elif the next neighbor is the dest
               set annotate = finish
               add path cost to cost
           else
               duplicate the current node
               add neighbor to current_list
               add path cost to cost
           delete the current tuple
   

在我们的案例中，

(src=A, cost=None, current_list=A, dest=B, annotate=continue)
 =>
(src=A, cost=1, current_list=AB, dest=B, annotate=finish)
(src=A, cost=1, current_list=AC, dest=B, annotate=continue)
(src=A, cost=None, current_list=A, dest=C, annotate=continue)
=>
(src=A, cost=1, current_list=AC, dest=C, annotate=finish)
(src=A, cost=1, current_list=AB, dest=C, annotate=continue)
(src=B, cost=None, current_list=B, dest=C, annotate=continue)
=>
(src=B, cost=1, current_list=BC, dest=C, annotate=finish)
(src=B, cost=1, current_list=BA, dest=C, annotate=continue)

3. 减少

   注意：我们减少src、dest对，并将其用作密钥对于元组列表中的每个元组

   if annotate == finish
       keep trace of min cost and delete tuple for each src dest pair that is not the current min
       then pass the current min as result
   elif annotate == delete
       delete the tuple
   else
       pass down to the next round of map
   

4. 映射

由于我们仍然有一些元组具有annotate=continue

(src=B, cost=1, current_list=BA, dest=C, annotate=continue)  
=>
(src=B, cost=2, current_list=BAC, dest=C, annotate=finish)  
(src=B, cost=2, current_list=BAB, dest=C, annotate=delete)  

(src=A, cost=1, current_list=AC, dest=B, annotate=continue)
=>
(src=A, cost=2, current_list=ACB, dest=B, annotate=finish)
(src=A, cost=2, current_list=ACA, dest=B, annotate=delete)
(src=A, cost=1, current_list=AB, dest=C, annotate=continue)
=>
(src=A, cost=2, current_list=ABC, dest=C, annotate=finish)
(src=A, cost=2, current_list=ABA, dest=C, annotate=delete)

5. 减少

我们没有连续元组，现在我们只使用reduce来查找每个src-dest对

Answer 1

Floyd-Warshall的内部两个循环本质上是矩阵乘法，加法用min代替，乘法用加法代替。你可以用map reduce做矩阵乘法，所以你可以用|V|map reduces实现Floyd-Warshall。

来自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|映射减少。

Answer 2

我想提出以下方法-通过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"}, ...]

实际上，在组合之后，每个源都将与一个目标节点列表相关联：列表可能包含重复的目标节点（重复的目标结点，只是对应不同的可能路径）。

所以，我们只需要从目标节点列表中删除重复的节点（只保留对应于最短路径的目标节点）。

上面的两段-实际上描述了减少步骤。reduce step-的输出与映射步骤的输入相同。

所以，最后，只需重复这些映射减少步骤，直到收敛。