每週學點大資料｜No.45 基於路徑的圖演算法
轉載聲明
編者按：燈塔大資料將每週持續推出《從零開始學大資料演算法》的連載，本書為哈爾濱工業大學著名教授王宏志老師的扛鼎力作，以對話的形式深入淺出的從何為大資料說到大資料演算法再到大資料技術的應用，
上期回顧&查看方式：
在上一期中，我們學習了用MapReduce 框架，以平行計算的觀點來解決一些圖論問題。在這一期中，我們看一類具體的問題，這類問題叫作基於路徑的圖演算法。這類演算法的目標是計算節點間關於路徑的資訊。
PS：瞭解上期詳細內容，請在自訂功能表列中點擊“燈塔資料”—“技術連載”進行查看；或者滑到文末【往期推薦】查看。
No.45期
基於路徑的圖演算法
Mr. 王：接下來我們看一類具體的問題，這類問題叫作基於路徑的圖演算法。這類演算法的目標是計算節點間關於路徑的資訊。在這類問題中，圖中的邊一般是加權的，這些權也可以叫作邊的標記，包括代價、距離、或者相似性等。
小可：邊的標記就像社交網路圖裡面的聯繫親密度一樣吧。
Mr. 王：是的。這類問題的典型例子就是單源最短路徑、最小生成樹、Steiner 樹、拓撲排序等。
小可：Steiner 樹我沒有聽說過，它是做什麼用的呢？
Mr. 王：Steiner 樹是連接給定集合的最小代價樹，後面會再提到它的。這裡我們要考慮的核心問題就是，如何將這些演算法並行化，以解決對比較大的圖的操作演算法。
現在我用單源最短路徑作為例子來說明如何發現計算過程中的並行化。
解決這個問題的經典演算法是Dijkstra 演算法。
Dijkstra 演算法是由圖靈獎獲得者、荷蘭人Dijkstra 提出的，是一個非常經典的求解單源最短路徑的演算法。它求解的問題是這樣定義的：在一個加權有向圖G=(V,E) 中，每一條邊都有一個非負實數作為它的權，在圖中我們標定一個源點u，去求解u 到圖中其他所有頂點的最短距離，也就是最短路徑的長度。
小可：這個演算法還是非常實用的啊，
單源最短路徑就能求解出一個城市到其他城市的最短距離。
Mr. 王：我們先給出這個演算法的偽代碼，然後再做解釋。它的輸入是圖G、起始點u 和總節點數n。
Dijkstra(G,u,n)
{
將u 加入到集合S 中 ①
對於G 中的每一個節點n，將u 到n 的最短距離SP[n] 設為u 與n 設為鄰接矩陣A[u][n] 中的值 ②
迴圈執行n-1 次 ③
{
從圖G 的V-S 中選出一個SP[i] 最小的頂點i，將其加入到S 中 ④
對於V-S 中的每一個頂點j
{
SP[j] = min (SP[j],SP[i]+A[i][j]) ⑤
}
}
}
我們來分析一下這個演算法。
①處：將初始節點u 加入到集合S 中。此處的集合S 表示的是我們已經訪問過的節點，在演算法開始時，僅有初始節點被訪問過。
②處：這是一個初始化操作，將最短距離先設為源點直接可以到達的頂點的邊的長度。至於不可達的那些頂點，則設為鄰接矩陣中的值∞，它不會對後面的較小值比較造成任何影響。
③處：由於除了u 之外，還有n-1 個頂點，所以一共要執行n-1 次。
④處：開始對還沒有被訪問過的頂點（V-S 中的那些頂點）進行訪問，要選擇目前距離它比較近的那些頂點，因為它們更傾向於説明發現更近的路徑，所以我們是按照距離從小到大的順序來選擇頂點的。
⑤處：當引入了節點i 之後，我們要看它的引入是不是引起了更短距離路徑的發現，所以要比較先經過I，再由(i,j) 這條邊抵達j 的路徑是不是比當前認為的到j 的最短距離更短一些，如果是，則說明i 的引入幫助發現了一條更短的路徑，我們就更新到j 的最短距離；否則，維持原來的最短路徑值即可。
迴圈結束時，SP[j] 中的值就是源點u 到j 的最短距離。
小可：還是挺好理解的，而且設計得非常巧妙啊。
Mr. 王：想想看，這個演算法的時間複雜度如何？
小可：假設圖中有n 個頂點，這個演算法有兩層迴圈：外層迴圈需要執行n-1 次；內層迴圈的執行是節點數目的線性函數，所以內層迴圈為O(n)。綜合起來，兩層迴圈就是O(n2)。
Mr. 王：不過你只說對了一半。當我們使用鄰接矩陣表示一個圖時，它的時間複雜度是O(n2) ；但如果圖比較稀疏，邊數非常少的話，則還可以嘗試用鄰接表來表示這個有向圖。此時，內迴圈可以稍作修改，針對邊去進行訪問，沿著與i 相關的鄰接表進行訪問，這樣算來，運行的時間與跟i 相關的邊數相關，所有節點的邊合成起來就會和圖的邊數呈線性關係，也就是O(e)。
小可：哦，原來還有這樣的考慮。以後在研究圖演算法的複雜度時，要多考慮圖的稀疏與稠密，還有圖的實際存儲結構，這些都會對演算法的複雜度產生影響。
Mr. 王：記憶體版本的Dijkstra 演算法每次沿著一個中間節點遍歷圖，基於總路徑的長度去定義遍歷的優先順序。相當於在這一過程中我們建立一個堆，每次取出堆頂進行處理。在這裡面就沒有發現並行機制，因為我們每次處理的都是所維護的這個堆的堆頂，每次都在對一個新的頂點進行操作。
為了提升計算效率，我們就要嘗試去挖掘其中可能並行的地方。可以想到，從源點出發，能不能不必每次只處理一個頂點，而是每次同時處理一個跳數的節點。比如，第一次處理從源點出發的1 跳節點，第二次可以從這些1 跳節點出發，去發現那些距離源點2 跳的節點，而這些工作之間並不會產生干擾。這樣思考的好處在於，我們能夠借此發現其中潛在的並行性。並行性在於在下一步開始之前，我們對本輪的這些節點的訪問是可以並行進行的。
在傳統的演算法中，對於Dijkstra 演算法仔細考察每個u，在其維護的堆中找到堆頂，從而可以安全地刪除確定頂點。這部分內容前面已經提到過了，現在要考慮的就是在MapReduce 中，我們怎麼去尋找其中潛在的並行性。
對每個v 考察所有潛在的u。
通過保存u 的前沿集合反覆運算計算（距離源點i 條邊）。
小可：那麼在MapReduce 中，具體是怎麼做的呢？
Mr. 王：先來想想，要建立一個MapReduce 解決方案，首先要定義什麼？
小可：我想應該是要定義出key-value 對吧。
Mr. 王：很好。在這個問題中，key-value 對是這樣定義的：一個頂點的編號ID 是它的key，而value 包含}> 這樣幾個部分
第一個資料欄表示從源點到節點ID 的最短路徑長度為∞。
第二個資料欄表示最短路徑上的下一個節點。
小可：嗯，這個時候，最短路徑多長還不知道，下一個節點也不知道，這裡都初始化成無窮和空。
Mr. 王：succ-node-ID，是其鄰居節點的ID，edge-cost 是到其鄰居節點的路徑長度。這兩部分其實就是節點ID 的鄰接表。
好了，接下來應該做什麼？
小可：接下來就要定義Map 和Reduce 了。
Mr. 王：嗯，掌握這種解決問題的思維方式，與理解演算法是同等重要的。
在Map 中，每一個Mapper 接收到的輸入都是ID 作為key,}>作為value 這樣的key-value 對。但是對於每一個ID 對應的succ-node-ID，我們傳送succ-node-ID 作為key，而{} 作為value 的key-value 對。這一步實際上是在做從源點到新發現的這個succ-node-ID 的路徑和路徑長度計算。
小可：這時我們是不是應該把最小的代價提取出來呢？
Mr. 王：不，這裡並不需要把最短的路徑提取出來，但是我們知道，最終要找的最短路徑一定包含在這裡面。即使提前找出這些最短的路徑，也並不一定是最終的最短路徑的一部分。
但是僅僅傳送這個還是不夠的，我們依然需要傳送ID,distance,{}這個key-value 對。想想看這是為什麼？
小可：如果還需要傳送這部分，則是因為在下一輪的反覆運算過程中還需要用到這些節點的原始資料。因為每一輪的反覆運算都和第一輪所做的計算並無本質區別，在計算下一輪的過程中，所使用的演算法和第一輪也是一樣的，依然是依賴如同第一輪那樣的輸入。
Mr. 王：很好。
小可：可是這樣傳送，到了最後節點ID 和其succ-node-ID 不是就都混到一起了嗎？
Mr. 王：嗯，是這樣，因為在Reduce 中，我們也確實需要這樣的機制。
在Reduce 之前，我們會根據ID 做一個Group，也就是將相同的ID 聚集到一起，然後進入Reduce，將相同IDdistance 定義為前驅節點中的最小代價，而next 定義為具有最小代價的那個前驅節點。最後將這樣的key-value 對傳送出去，也就是傳送ID 小可：嗯，似乎是懂了。 Mr. 王：哈哈，“似乎”可不行啊，我們舉個例子，把這個問題徹底搞清楚。
這是一個典型的最短路徑問題。
在第一輪反覆運算中，Mapper 傳送出去的資料是(a,) (c,)，a 和c 分別是s 的後繼節點，s 是源點，5 和10 是邊的權重。
在Reducer 中，我們求出了到a 和c 的當前最短路徑10 和5，按照之前我們定義的那種標記法，Reducer 會發送(a,) (c,) 這樣的資料。
接下來是第二輪反覆運算。
Mapper ：(a,) (c,) (a,) (c,) (b,) (b,) (d,)
Reducer ：(a,) (c,) (b,) (d,)
在第二輪反覆運算中，我們重啟一次MapReduce，注意看新增的資料記錄，(a,) 這條記錄表示，這一次發展到a 節點的鄰居是c，而之前到c 的最短路徑是5，a 到c 的距離是3，所以加起來s 到a 的當前最短路徑就是8。
小可：相應的，(b,) 表示發展到b 節點的鄰居是a，原來到a 的最短路徑是10，又因為a 到b 的距離是1，所以當前s 到b 的最短路徑就是11。
Mr. 王：很好，其他的也是這個道理。接下來在Reducer 中，我們對這些鍵值對進行基於key 的分組，這樣就能求出到當前這一輪反覆運算中各個可達節點的最短路徑。第三輪反覆運算還是同樣的道理。在這一輪反覆運算中，b、d 兩個節點如同上一輪反覆運算被加入了研究範圍，使用和上一輪反覆運算同樣的方法解出了當前到達每個節點的最短路徑長度。
Mapper ：(a,) (c,) (a,) (c,) (b,) (b,) (d,) (b,)(d,)
Reducer ：(a,) (c,) (b,) (d,)
這時我們還要進行一輪反覆運算，發現第四輪反覆運算和第三輪反覆運算的結果已經完全一致，於是認為整個演算法已經收斂了，無須繼續進行下去，也就得出了從s 出發到每一個節點的最短路徑。
下期精彩預告：
經過學習，我們掌握基於路徑的圖演算法，計算節點間關於路徑的資訊問題。在下一期中，我們將討論一個新話題——超越MapReduce 的並行大資料處理。更多精彩內容，敬請關注燈塔大資料，每週五不見不散呦！
文章編輯：柯一
【人工智慧】獲取人工智慧時代的發展思考 ppt
【網路安全】獲取國民網路安全報告全文
【 燈塔 】 查看更多關鍵字回復
還有n-1 個頂點，所以一共要執行n-1 次。④處：開始對還沒有被訪問過的頂點（V-S 中的那些頂點）進行訪問，要選擇目前距離它比較近的那些頂點，因為它們更傾向於説明發現更近的路徑，所以我們是按照距離從小到大的順序來選擇頂點的。
⑤處：當引入了節點i 之後，我們要看它的引入是不是引起了更短距離路徑的發現，所以要比較先經過I，再由(i,j) 這條邊抵達j 的路徑是不是比當前認為的到j 的最短距離更短一些，如果是，則說明i 的引入幫助發現了一條更短的路徑，我們就更新到j 的最短距離；否則，維持原來的最短路徑值即可。
迴圈結束時，SP[j] 中的值就是源點u 到j 的最短距離。
小可：還是挺好理解的，而且設計得非常巧妙啊。
Mr. 王：想想看，這個演算法的時間複雜度如何？
小可：假設圖中有n 個頂點，這個演算法有兩層迴圈：外層迴圈需要執行n-1 次；內層迴圈的執行是節點數目的線性函數，所以內層迴圈為O(n)。綜合起來，兩層迴圈就是O(n2)。
Mr. 王：不過你只說對了一半。當我們使用鄰接矩陣表示一個圖時，它的時間複雜度是O(n2) ；但如果圖比較稀疏，邊數非常少的話，則還可以嘗試用鄰接表來表示這個有向圖。此時，內迴圈可以稍作修改，針對邊去進行訪問，沿著與i 相關的鄰接表進行訪問，這樣算來，運行的時間與跟i 相關的邊數相關，所有節點的邊合成起來就會和圖的邊數呈線性關係，也就是O(e)。
小可：哦，原來還有這樣的考慮。以後在研究圖演算法的複雜度時，要多考慮圖的稀疏與稠密，還有圖的實際存儲結構，這些都會對演算法的複雜度產生影響。
Mr. 王：記憶體版本的Dijkstra 演算法每次沿著一個中間節點遍歷圖，基於總路徑的長度去定義遍歷的優先順序。相當於在這一過程中我們建立一個堆，每次取出堆頂進行處理。在這裡面就沒有發現並行機制，因為我們每次處理的都是所維護的這個堆的堆頂，每次都在對一個新的頂點進行操作。
為了提升計算效率，我們就要嘗試去挖掘其中可能並行的地方。可以想到，從源點出發，能不能不必每次只處理一個頂點，而是每次同時處理一個跳數的節點。比如，第一次處理從源點出發的1 跳節點，第二次可以從這些1 跳節點出發，去發現那些距離源點2 跳的節點，而這些工作之間並不會產生干擾。這樣思考的好處在於，我們能夠借此發現其中潛在的並行性。並行性在於在下一步開始之前，我們對本輪的這些節點的訪問是可以並行進行的。
在傳統的演算法中，對於Dijkstra 演算法仔細考察每個u，在其維護的堆中找到堆頂，從而可以安全地刪除確定頂點。這部分內容前面已經提到過了，現在要考慮的就是在MapReduce 中，我們怎麼去尋找其中潛在的並行性。
對每個v 考察所有潛在的u。
通過保存u 的前沿集合反覆運算計算（距離源點i 條邊）。
小可：那麼在MapReduce 中，具體是怎麼做的呢？
Mr. 王：先來想想，要建立一個MapReduce 解決方案，首先要定義什麼？
小可：我想應該是要定義出key-value 對吧。
Mr. 王：很好。在這個問題中，key-value 對是這樣定義的：一個頂點的編號ID 是它的key，而value 包含}> 這樣幾個部分
第一個資料欄表示從源點到節點ID 的最短路徑長度為∞。
第二個資料欄表示最短路徑上的下一個節點。
小可：嗯，這個時候，最短路徑多長還不知道，下一個節點也不知道，這裡都初始化成無窮和空。
Mr. 王：succ-node-ID，是其鄰居節點的ID，edge-cost 是到其鄰居節點的路徑長度。這兩部分其實就是節點ID 的鄰接表。
好了，接下來應該做什麼？
小可：接下來就要定義Map 和Reduce 了。
Mr. 王：嗯，掌握這種解決問題的思維方式，與理解演算法是同等重要的。
在Map 中，每一個Mapper 接收到的輸入都是ID 作為key,}>作為value 這樣的key-value 對。但是對於每一個ID 對應的succ-node-ID，我們傳送succ-node-ID 作為key，而{} 作為value 的key-value 對。這一步實際上是在做從源點到新發現的這個succ-node-ID 的路徑和路徑長度計算。
小可：這時我們是不是應該把最小的代價提取出來呢？
Mr. 王：不，這裡並不需要把最短的路徑提取出來，但是我們知道，最終要找的最短路徑一定包含在這裡面。即使提前找出這些最短的路徑，也並不一定是最終的最短路徑的一部分。
但是僅僅傳送這個還是不夠的，我們依然需要傳送ID,distance,{}這個key-value 對。想想看這是為什麼？
小可：如果還需要傳送這部分，則是因為在下一輪的反覆運算過程中還需要用到這些節點的原始資料。因為每一輪的反覆運算都和第一輪所做的計算並無本質區別，在計算下一輪的過程中，所使用的演算法和第一輪也是一樣的，依然是依賴如同第一輪那樣的輸入。
Mr. 王：很好。
小可：可是這樣傳送，到了最後節點ID 和其succ-node-ID 不是就都混到一起了嗎？
Mr. 王：嗯，是這樣，因為在Reduce 中，我們也確實需要這樣的機制。
在Reduce 之前，我們會根據ID 做一個Group，也就是將相同的ID 聚集到一起，然後進入Reduce，將相同IDdistance 定義為前驅節點中的最小代價，而next 定義為具有最小代價的那個前驅節點。最後將這樣的key-value 對傳送出去，也就是傳送ID 小可：嗯，似乎是懂了。 Mr. 王：哈哈，“似乎”可不行啊，我們舉個例子，把這個問題徹底搞清楚。
這是一個典型的最短路徑問題。
在第一輪反覆運算中，Mapper 傳送出去的資料是(a,) (c,)，a 和c 分別是s 的後繼節點，s 是源點，5 和10 是邊的權重。
在Reducer 中，我們求出了到a 和c 的當前最短路徑10 和5，按照之前我們定義的那種標記法，Reducer 會發送(a,) (c,) 這樣的資料。
接下來是第二輪反覆運算。
Mapper ：(a,) (c,) (a,) (c,) (b,) (b,) (d,)
Reducer ：(a,) (c,) (b,) (d,)
在第二輪反覆運算中，我們重啟一次MapReduce，注意看新增的資料記錄，(a,) 這條記錄表示，這一次發展到a 節點的鄰居是c，而之前到c 的最短路徑是5，a 到c 的距離是3，所以加起來s 到a 的當前最短路徑就是8。
小可：相應的，(b,) 表示發展到b 節點的鄰居是a，原來到a 的最短路徑是10，又因為a 到b 的距離是1，所以當前s 到b 的最短路徑就是11。
Mr. 王：很好，其他的也是這個道理。接下來在Reducer 中，我們對這些鍵值對進行基於key 的分組，這樣就能求出到當前這一輪反覆運算中各個可達節點的最短路徑。第三輪反覆運算還是同樣的道理。在這一輪反覆運算中，b、d 兩個節點如同上一輪反覆運算被加入了研究範圍，使用和上一輪反覆運算同樣的方法解出了當前到達每個節點的最短路徑長度。
Mapper ：(a,) (c,) (a,) (c,) (b,) (b,) (d,) (b,)(d,)
Reducer ：(a,) (c,) (b,) (d,)
這時我們還要進行一輪反覆運算，發現第四輪反覆運算和第三輪反覆運算的結果已經完全一致，於是認為整個演算法已經收斂了，無須繼續進行下去，也就得出了從s 出發到每一個節點的最短路徑。
下期精彩預告：
經過學習，我們掌握基於路徑的圖演算法，計算節點間關於路徑的資訊問題。在下一期中，我們將討論一個新話題——超越MapReduce 的並行大資料處理。更多精彩內容，敬請關注燈塔大資料，每週五不見不散呦！
文章編輯：柯一
【人工智慧】獲取人工智慧時代的發展思考 ppt
【網路安全】獲取國民網路安全報告全文
【 燈塔 】 查看更多關鍵字回復