什麼是使用map reduce通過bfs遍歷圖的有效方式？

Question

這是一個面試問題我被招聘者問，這個問題基本上是計算每一個節點的所有節點的最短路徑，而我的解決方案是以下

啓動所有可能的邊緣（沒有扭轉 - B是一樣的BA）

每個節點將在以下（SRC，成本，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 

的招聘人員說，這是沒有效率的，我可以看到這一點，因爲你穿越combinatorialy如何效率不高，但我能想到的唯一的選擇是，如果您有n個節點，然後產卵n個服務器，並且爲招聘人員所說的每個節點做dijkstra也是錯誤的。有人可以幫我解決這個問題嗎？

編輯：

Ex。三角圖形

的邊緣AB，BC，CA與算法

1. 首先，我們開始考慮到所有可能的源目的地對保持優勢的是反向的1

   路徑成本不是唯一的 AB ，AC，BC（BA，CA，BC被省略）

對於每個源 - 目的地對我們有以下的元組

(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) 

現在我們開始在地圖減少算法

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) 

減少

注意：我們減少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 

地圖

因爲我們還是有一定的元組有註釋=繼續

(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

我們沒有繼續元組，現在我們只使用reduce來找到每個src dest對的最小值

Answer 1

Floyd-Warshall的內部兩個循環基本上是矩陣乘法，其中加法由加法替代，乘法由加法替換。你可以用map-reduce做矩陣乘法，所以你可以用| V |實現Floyd Warshall地圖降低。

從上弗洛伊德-沃肖爾Wikipedia頁面：

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（path："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"}, ...]

事實上，合併後 - 每個源將與目標節點的列表關聯： 列表可能包含重複的目標節點（重複的目標節點，只對應於不同的可能路徑）。因此，我們只需要從目標節點列表中刪除重複項（僅保留與最短路徑相對應的目標節點）。

從上面兩段 - 實際上描述了減少步驟。 減少步驟的輸出 - 與輸入到的地圖步驟相同。

因此，最後 - 只需重複這些map-reduce步驟，直到收斂。