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

Question

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

发起所有可能的边(无反A-B与B-A相同)

每个节点将在下面表示 (src, cost, current_list, dest) ，src 和 dest 基本上是我们之前发起的所有可能的边缘

map :

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招聘人员说的也是错误的。有人可以帮我解决这个问题吗？

编辑:

例。三角图

边是 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)

1. 现在我们开始map reduce算法

   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)

1. 减少

   注意:我们减少了 src，dest 对，并将其用作我们的 key 对于元组列表中的每个元组

   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
   

2. map

因为我们还有一些具有 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)

1. 减少

我们没有连续的元组，现在我们只使用 reduce 找到每个 src dest 对的最小值

Answer 1

Floyd-Warshall 的内部两个循环本质上是矩阵乘法，用 min 代替加法，用加法代替乘法。您可以使用 map-reduce 进行矩阵乘法，因此您可以使用 |V| 实现 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 行)在结构上与矩阵乘法相同，您可以在 map- reduce”解决方案来执行此操作。

外层 (k) 循环变为 |V|映射减少。