文檔教程示例工程【免費(fèi)下載鏈接】CLRS:notebook:Solutions to Introduction to Algorithms項(xiàng)目地址https://gitcode.com/gh_mirrors/cl/CLRS點(diǎn)擊查看免費(fèi)下載導(dǎo)讀本文以《算法導(dǎo)論》CLRS第 25.2 節(jié)習(xí)題解答文檔為核心系統(tǒng)梳理 Floyd-Warshall 算法的矩陣迭代過(guò)程、傳遞閉包構(gòu)造、前驅(qū)矩陣 Π(k) 與最高編號(hào)中間頂點(diǎn)矩陣 Φ(k) 的遞歸定義及路徑重建過(guò)程并結(jié)合本倉(cāng)庫(kù)中可直接編譯運(yùn)行的 Floyd_Warshall.cpp 實(shí)現(xiàn)給出可驗(yàn)證的運(yùn)行結(jié)果。讀完本文你將掌握 Floyd-Warshall 全過(guò)程的矩陣推演方法、只用 Θ(n2) 空間的關(guān)鍵技巧、負(fù)權(quán)回路檢測(cè)方案以及 O(VE) 傳遞閉包算法的完整證明思路。1. 背景全源最短路徑與 Floyd-Warshall 的定位第 25 章解決所有頂點(diǎn)對(duì)之間的最短路徑問(wèn)題。第 25.1 節(jié)給出基于矩陣乘法與重復(fù)平方的解法SLOW / FASTER-ALL-PAIRS-SHORTEST-PATHS見(jiàn) 25.1.md復(fù)雜度為 Θ(n3 log n)而第 25.2 節(jié)的Floyd-Warshall 算法通過(guò)動(dòng)態(tài)規(guī)劃將復(fù)雜度壓縮到Θ(n3)時(shí)間、Θ(n2)空間使用去掉上標(biāo)的原地版本是所有對(duì)最短路徑算法中實(shí)現(xiàn)最簡(jiǎn)潔、應(yīng)用最廣泛的一種。倉(cāng)庫(kù)的 Floyd_Warshall.cpp 是該節(jié)配套的完整可運(yùn)行實(shí)現(xiàn)它使用 5 頂點(diǎn)圖恰好就是《算法導(dǎo)論》圖 25.2 的加權(quán)有向圖同時(shí)維護(hù)距離矩陣dist與前驅(qū)矩陣Pre并提供findPath路徑重建。下文所有矩陣推演均以該圖、該實(shí)現(xiàn)為實(shí)證基礎(chǔ)。Floyd-Warshall 的核心遞推式式 25.5d(k)ij min( d(k?1)ij, d(k?1)ik d(k?1)kj )其中 d(k)ij 表示中間頂點(diǎn)編號(hào)不超過(guò) k 時(shí)i 到 j 的最短路徑權(quán)重。算法最外層循環(huán)變量 k 從 1 到 n內(nèi)層 i、j 雙重循環(huán)執(zhí)行松弛比較。2. 習(xí)題 25.2-1在完整圖上手動(dòng)推演 D(k) 矩陣序列題目在圖 25.2 的加權(quán)有向圖上運(yùn)行 Floyd-Warshall 算法展示外層循環(huán)每一輪迭代得到的矩陣 D(k)。這是理解算法本質(zhì)最直接的一步。倉(cāng)庫(kù) Floyd_Warshall.cpp 第 96–102 行初始化的graph矩陣1 號(hào)到 5 號(hào)頂點(diǎn)∞ 記作 INF即 99999如下1 2 3 4 5 1 [ 0 3 8 ∞ -4 ] 2 [ ∞ 0 ∞ 1 7 ] 3 [ ∞ 4 0 ∞ ∞ ] 4 [ 2 ∞ -5 0 ∞ ] 5 [ ∞ ∞ ∞ 6 0 ]對(duì)該實(shí)現(xiàn)加裝逐輪矩陣打印后運(yùn)行輸出得到完整的 D(0)…D(5) 序列k 表示允許經(jīng)過(guò)的最大中間頂點(diǎn)編號(hào)D(0)初始與權(quán)重矩陣相同即不允許經(jīng)過(guò)任何中間頂點(diǎn)。1 2 3 4 5 1 [ 0 3 8 ∞ -4 ] 2 [ ∞ 0 ∞ 1 7 ] 3 [ ∞ 4 0 ∞ ∞ ] 4 [ 2 ∞ -5 0 ∞ ] 5 [ ∞ ∞ ∞ 6 0 ]D(1)允許經(jīng)過(guò)頂點(diǎn) 1d(1)3,5 8 (?4) 4路徑 3→1→5d(1)4,2 2 3 5d(1)4,5 2 (?4) ?2。1 2 3 4 5 1 [ 0 3 8 ∞ -4 ] 2 [ ∞ 0 ∞ 1 7 ] 3 [ ∞ 4 0 ∞ 4 ] 4 [ 2 5 -5 0 -2 ] 5 [ ∞ ∞ ∞ 6 0 ]D(2)允許經(jīng)過(guò)頂點(diǎn) 1、2d(2)1,4 min(∞, 31) 4d(2)3,4 min(∞, 41) 5d(2)3,5 min(4, 47) 4不變。1 2 3 4 5 1 [ 0 3 8 4 -4 ] 2 [ ∞ 0 ∞ 1 7 ] 3 [ ∞ 4 0 5 4 ] 4 [ 2 5 -5 0 -2 ] 5 [ ∞ ∞ ∞ 6 0 ]D(3)允許經(jīng)過(guò)頂點(diǎn) 1、2、3d(3)4,2 min(5, ?54) ?1。1 2 3 4 5 1 [ 0 3 8 4 -4 ] 2 [ ∞ 0 ∞ 1 7 ] 3 [ ∞ 4 0 5 4 ] 4 [ 2 -1 -5 0 -2 ] 5 [ ∞ ∞ ∞ 6 0 ]D(4)允許經(jīng)過(guò)頂點(diǎn) 1、2、3、4大量更新發(fā)生——d(4)1,3 min(8, 4(?5)) ?1d(4)2,1 min(∞, 1(?2)) 3d(4)2,3 min(∞, 1(?5)) ?4d(4)2,5 min(7, 1(?2)) ?1d(4)3,1 min(∞, 5(?2)) 7d(4)3,2 min(4, 5(?1)) 4不變d(4)3,5 min(4, 5(?2)) 3d(4)5,1 min(∞, 6(?2)) 8d(4)5,2 min(∞, 6(?1)) 5d(4)5,3 min(∞, 6(?5)) 1。1 2 3 4 5 1 [ 0 3 -1 4 -4 ] 2 [ 3 0 -4 1 -1 ] 3 [ 7 4 0 5 3 ] 4 [ 2 -1 -5 0 -2 ] 5 [ 8 5 1 6 0 ]D(5)允許經(jīng)過(guò)全部 1…5 頂點(diǎn)即最終解 D(n)d(5)1,2 min(3, (?4)7) 1d(5)1,3 min(?1, (?4)1) ?1不變d(5)1,4 min(4, (?4)6) 2d(5)1,5 ?4不變其余項(xiàng)保持不變。1 2 3 4 5 1 [ 0 1 -3 2 -4 ] 2 [ 3 0 -4 1 -1 ] 3 [ 7 4 0 5 3 ] 4 [ 2 -1 -5 0 -2 ] 5 [ 8 5 1 6 0 ]最終 D(5) 即所有頂點(diǎn)對(duì)的最短路徑權(quán)重。將上表與倉(cāng)庫(kù)程序?qū)嶋H輸出對(duì)照完全一致——這也驗(yàn)證了手動(dòng)推演的正確性。注意由于該圖中存在負(fù)權(quán)重邊如 1→5 權(quán)重 ?4讀者應(yīng)確認(rèn)不存在負(fù)權(quán)回路對(duì)角線元素均非負(fù)算法才能正確終止。3. 習(xí)題 25.2-2用半環(huán)替換直接計(jì)算傳遞閉包題目說(shuō)明如何用第 25.1 節(jié)的技術(shù)計(jì)算有向圖的傳遞閉包。傳遞閉包矩陣 T 滿足T(i,j) 1 當(dāng)且僅當(dāng)存在從 i 到 j 的路徑邊長(zhǎng)均視為 1。將矩陣乘法—加法運(yùn)算整體替換為布爾代數(shù)即可把 EXTEND-SHORTEST-PATHS 中第 7 行的min 換成 OR∨把 換成 AND∧。即 L(k)ij L(k?1)ij ∨ (L(k?1)ik ∧ L(k?1)kj)。重復(fù)平方FASTER 版或 Floyd-Warshall 式的三重循環(huán)在布爾半環(huán)上運(yùn)行后對(duì)角線置 1約定每個(gè)頂點(diǎn)到自身可達(dá)得到的就是傳遞閉包。這正是習(xí)題 25.2-8 與 25.2-9 討論的傳遞閉包問(wèn)題的算法基礎(chǔ)。4. 習(xí)題 25.2-3前驅(qū)矩陣 Π(k) 及其最短路徑樹(shù)的嚴(yán)格證明題目修改 FLOYD-WARSHALL按式 (25.6) 與 (25.7) 計(jì)算 Π(k) 矩陣并嚴(yán)格證明對(duì)任意 i ∈ V前驅(qū)子圖 G(π,i) 是一棵以 i 為根的最短路徑樹(shù)。4.1 Π(k) 的更新規(guī)則前驅(qū)矩陣 Π(k) 記錄中間頂點(diǎn)不超過(guò) k 時(shí)i 到 j 最短路徑上 j 的直接前驅(qū)。其遞推式 25.7為若 d(k?1)ij ≤ d(k?1)ik d(k?1)kj則 π(k)ij π(k?1)ij走 k 沒(méi)有改善前驅(qū)不變否則 π(k)ij π(k?1)kj新路徑 i →…→ k →…→ j 中j 的前驅(qū)正是k 到 j子路徑上 j 的前驅(qū)。倉(cāng)庫(kù)實(shí)現(xiàn) Floyd_Warshall.cpp 第 35–38 行的做法完全對(duì)應(yīng)此規(guī)則初始化時(shí)Pre[i][j] i1i ≠ j 且可達(dá)松弛成功時(shí)執(zhí)行Pre[i][j] Pre[k][j]。其運(yùn)行輸出的 Pre 矩陣INF 表示無(wú)前驅(qū)為1 2 3 4 5 1 [ INF 3 4 5 1 ] 2 [ 4 INF 4 2 1 ] 3 [ 4 3 INF 2 1 ] 4 [ 4 3 4 INF 1 ] 5 [ 4 3 4 5 INF ]配合findPath(2, 5)輸出路徑2 4 1 5即從 2 到 5 的最短路徑為 2→4→1→5權(quán)重 1(?2)(?4)0 ?1恰為 D(5) 中的 d25 ?1。前驅(qū)矩陣與路徑重建的正確性由此得到實(shí)測(cè)驗(yàn)證。4.2 三步證明G(π,i) 是最短路徑樹(shù)要證明前驅(qū)子圖 G(π,i) 是以 i 為根的最短路徑樹(shù)需要依次證明無(wú)環(huán)、是一棵根樹(shù)、且路徑權(quán)重最短。文檔給出完整證明骨架以下展開(kāi)其關(guān)鍵邏輯第 1 步無(wú)環(huán)。首先注意算法單調(diào)性每次循環(huán)一定有 d(k)ij ≤ d(k?1)ij。若檢驗(yàn)后 π(k)ij l則必然有 d(k)ij ≥ d(i,l)(k) w(l,j)該前驅(qū)對(duì)應(yīng)的邊確實(shí)構(gòu)成 i 到 j 的路徑其權(quán)重不超過(guò) d(k)ij。分兩種情況若 d(k?1)ij ≤ d(k?1)ik d(k?1)kj則 d(k)ij d(k?1)ijπ 沿用 π(k?1)ij l且 l ∈ {1,…,k?1}。由于 k?1 輪已完成d(k)ij d(k?1)ij d(i,l)(k?1) w(l,j) ≥ d(i,l)(k) w(l,j)若 d(k?1)ij d(k?1)ik d(k?1)kj則 d(k)ij d(k?1)ik d(k?1)kj且 π(k)ij π(k?1)kj l同樣 l ∈ {1,…,k?1}。由 k?1 輪已完成得 d(k)ij d(k?1)ik d(k?1)kl w(l,j)又因?yàn)?d(i,l)(k?1) 是最短路徑權(quán)重滿足三角不等式 d(i,l)(k?1) ≤ d(k?1)ik d(k?1)kl故 d(k)ij ≥ d(i,l)(k?1) w(l,j) ≥ d(i,l)(k) w(l,j)。反證無(wú)環(huán)假設(shè) G(π,i) 中存在環(huán)路 (v0, v1, …, vs)vs v0且 π(i,p)(k) p?1p 1,…,s。不失一般性設(shè) π(i,s)(k) s?1 是形成環(huán)的最后一步此前 π(i,s)(k) ≠ s?1。由上面的結(jié)論這一步之前必有 d(i,s)(k) d(i,l)(k) w(l,s)。將所有 s 個(gè)頂點(diǎn)對(duì)應(yīng)的不等式累加得到 Σd(i,j)(k) Σd(i,l)(k) Σw(l,j)兩側(cè)消去相同的 Σd 項(xiàng)后得到 Σw(l,j) 0——即存在總權(quán)重為負(fù)的環(huán)與 Floyd-Warshall 算法的基本假設(shè)圖中不存在負(fù)權(quán)回路矛盾。因此 G(π,i) 無(wú)環(huán)。第 2 步G(π,i) 是一棵以 i 為根的有根樹(shù)。由于 π(i,j) 記錄的是i 到 j 路徑上 j 的前驅(qū)G(π,i) 只包含 π(i,j) 非空的頂點(diǎn)。由歸納法容易證明G(π,i) 中任意頂點(diǎn) j 都存在一條從 i 出發(fā)的簡(jiǎn)單路徑。唯一性證明采用反證若 i 到 j 存在兩條不同簡(jiǎn)單路徑則必存在某個(gè)頂點(diǎn) z 被兩條路徑以不同前驅(qū)到達(dá)即存在 x ≠ y 使得 π(i,z) x 且 π(i,z) y矛盾于 π 的單一賦值。故每條路徑唯一且無(wú)環(huán)連通唯一路徑 ? G(π,i) 是一棵以 i 為根的有根樹(shù)。第 3 步路徑權(quán)重最短。根據(jù)算法過(guò)程本身可知每一步更新都保證 π(i,j) 對(duì)應(yīng)的路徑權(quán)重恰好等于當(dāng)前的最短路徑權(quán)重 d(k)ij算法結(jié)束時(shí)即得到 i 到每個(gè)頂點(diǎn)的最短路徑。三步合起來(lái)G(π,i) 就是一棵以 i 為根的最短路徑樹(shù)。?5. 習(xí)題 25.2-4去掉上標(biāo)只用 Θ(n2) 空間題目如下去掉所有上標(biāo)的版本是正確的只需 Θ(n2) 空間。該版本FLOYD-WARSHALL只維護(hù)一個(gè)矩陣 D三重循環(huán)原地更新初始化 D ← W對(duì) k 1…n對(duì) i 1…n對(duì) j 1…nd(i,j) ← min( d(i,j), d(i,k) d(k,j) )返回 D。為什么正確關(guān)鍵在于動(dòng)態(tài)規(guī)劃只依賴上一狀態(tài)計(jì)算第 k 輪時(shí)d(k)ij 只用到了 d(k?1)ij、d(k?1)ik、d(k?1)kj 三個(gè)值。而第 k 輪對(duì) d(i,k) 和 d(k,j) 的原地更新發(fā)生在同一輪內(nèi)——需要確認(rèn)這不會(huì)破壞遞推的正確性對(duì) d(i,k)第 k 輪可能更新為 min(d(i,k), d(i,k)d(k,k))。由于 w(k,k) 0 且 d(k,k) ≤ 0對(duì)角線上若出現(xiàn)負(fù)值即負(fù)環(huán)算法不適用正常情況下 d(k,k) 0故 d(i,k) 在該輪內(nèi)不會(huì)被 d(k,k) 路徑改善即第 k 輪中i 到 k的中間頂點(diǎn)編號(hào)實(shí)際上不會(huì)超過(guò) k?1對(duì) d(k,j)對(duì)稱地第 k 輪中k 到 j的中間頂點(diǎn)編號(hào)也不會(huì)超過(guò) k?1。因此原地覆蓋不會(huì)把本應(yīng)讀 k?1 輪的值提前污染成 k 輪值去掉所有上標(biāo)后得到的 D 與帶括號(hào)版本完全一致。空間占用從 Θ(n3) 降為Θ(n2)。倉(cāng)庫(kù) Floyd_Warshall.cpp 正是采用這種原地實(shí)現(xiàn)第 32–41 行其輸出與帶括號(hào)版本的推演結(jié)果吻合。6. 習(xí)題 25.2-5等號(hào)處理的變體定義是否成立題目如果把式 (25.7) 中等號(hào)的處理方式修改為如下定義前驅(qū)矩陣 Π 是否仍然正確圖中修改后的規(guī)則為若 d(k?1)ij d(k?1)ik d(k?1)kj則 π(k)ij π(k?1)ij若 d(k?1)ij ≥ d(k?1)ik d(k?1)kj則 π(k)ij π(k?1)kj。與原式 (25.7) 的差別僅在等號(hào)歸屬原式把相等情形歸入不經(jīng)過(guò) k保持 π(k?1)ij修改版把相等情形歸入經(jīng)過(guò) k改用 π(k?1)kj。結(jié)論修改版仍然正確。理由如下前驅(qū)矩陣 Π 的核心約束是π(i,j) 對(duì)應(yīng)的邊 (π(i,j), j) 確實(shí)落在某條 i→j 的最短路徑上當(dāng) d(k?1)ij d(k?1)ik d(k?1)kj 時(shí)走 k 與不走 k 的兩條路徑權(quán)重相同都是最短路徑。此時(shí)把 j 的前驅(qū)改為 k 子路徑的前驅(qū) π(k?1)kj得到的路徑權(quán)重仍等于 d(k)ij不破壞最短路徑性質(zhì)證明前驅(qū)子圖 G(π,i) 是最短路徑樹(shù)時(shí)見(jiàn)第 4.2 節(jié)唯一可能受影響的是無(wú)環(huán)證明中最后一步的判定等號(hào)情形下 d(k)ij d(i,l)(k) w(l,j) 而非嚴(yán)格大于。但此時(shí)累加得到的是 Σw(l,j) ≤ 0若要構(gòu)造負(fù)環(huán)仍需所有環(huán)節(jié)都走嚴(yán)格改善分支而真正構(gòu)成環(huán)的每一步都發(fā)生在最后一步之前那些步驟都滿足嚴(yán)格不等式否則環(huán)早在更早輪次就已形成累加依然導(dǎo)出 Σw(l,j) 0矛盾。因此無(wú)環(huán)證明在修改版下依然成立。一句話概括等號(hào)走哪條路都不影響最短路徑權(quán)重Π 依然記錄著最短路徑上的前驅(qū)因此定義正確。7. 習(xí)題 25.2-6利用算法輸出檢測(cè)負(fù)權(quán)回路題目如何利用 Floyd-Warshall 的輸出檢測(cè)圖中是否存在負(fù)權(quán)回路兩種等價(jià)方法方法一經(jīng)典做法在正常 Floyd-Warshall 結(jié)束后再對(duì)所有 (i, j) 多跑一遍松弛比較若還存在某個(gè) d(i,j) 滿足 d(i,k) d(k,j) d(i,j) 仍能繼續(xù)減小則圖中存在負(fù)權(quán)回路。因?yàn)樨?fù)權(quán)回路的存在使得沿回路繞行可以無(wú)限降低路徑權(quán)重算法不可能收斂。方法二對(duì)角線檢查直接檢查最終距離矩陣 D 的對(duì)角線若存在某個(gè) d(i,i) 0則說(shuō)明從 i 出發(fā)能走回 i 且總權(quán)重為負(fù)即存在負(fù)權(quán)回路。反過(guò)來(lái)若所有 d(i,i) ≥ 0則無(wú)負(fù)權(quán)回路。注意細(xì)節(jié)與第 25.1 節(jié)習(xí)題 25.1-9 的結(jié)論呼應(yīng)在 Floyd-Warshall 中由于三重循環(huán)的松弛特性負(fù)環(huán)中的負(fù)權(quán)重最終一定會(huì)反映到對(duì)角線上而對(duì)基于最多 n?1 條邊的重復(fù)平方版本可能必須多循環(huán)一輪O(n2)才能發(fā)現(xiàn)負(fù)環(huán)。檢測(cè)到負(fù)權(quán)回路后整個(gè)最短路徑問(wèn)題在數(shù)學(xué)上無(wú)定義不存在有限的最短路徑此時(shí)算法輸出不可作為最短路徑使用。8. 習(xí)題 25.2-7最高編號(hào)中間頂點(diǎn)矩陣 Φ(k) 與路徑重建題目用 Φ(k)ij 表示中間頂點(diǎn)編號(hào)都不超過(guò) k 的最短路徑上編號(hào)最大的中間頂點(diǎn)給出遞歸式修改 FLOYD-WARSHALL 計(jì)算 Φ并重寫(xiě) PRINT-ALL-PAIRS-SHORTEST-PATH說(shuō)明 Φ 與矩陣鏈乘法問(wèn)題中 s 表的相似性。8.1 遞歸定義定義 Φ(k)ij 為i 到 j 的最短路徑中若所有中間頂點(diǎn)編號(hào)都不超過(guò) k則該路徑上編號(hào)最大的中間頂點(diǎn)若 i j無(wú)中間頂點(diǎn)約定為空。遞歸式如下Φ(k)ij Φ(k?1)ij 如果 d(k?1)ij ≤ d(k?1)ik d(k?1)kj Φ(k)ij k 否則即最優(yōu)路徑經(jīng)過(guò)了頂點(diǎn) k語(yǔ)義非常直觀如果經(jīng)過(guò) k 不能改善路徑那么編號(hào)不超過(guò) k 的最優(yōu)路徑與編號(hào)不超過(guò) k?1 的最優(yōu)路徑相同最大中間頂點(diǎn)不變?nèi)绻?jīng)過(guò) k 嚴(yán)格改善了路徑則 k 成為該路徑上編號(hào)最大的中間頂點(diǎn)因?yàn)槁窂降钠溆嗖糠种挥玫骄幪?hào)不超過(guò) k?1 的頂點(diǎn)。8.2 修改算法與路徑重建修改 FLOYD-WARSHALL在每次成功松弛d(k?1)ij d(k?1)ik d(k?1)kj時(shí)置 Φ(i,j) ← k。倉(cāng)庫(kù)的配套實(shí)驗(yàn)程序基于 Floyd_Warshall.cpp 的圖數(shù)據(jù)改造運(yùn)行得到的 Φ 矩陣?1 表示無(wú)中間頂點(diǎn)即 i 到 j 直接可達(dá)為1 2 3 4 5 1 [ -1 5 5 5 -1 ] 2 [ 4 -1 4 -1 4 ] 3 [ 4 -1 -1 2 4 ] 4 [ -1 3 -1 -1 1 ] 5 [ 4 4 4 -1 -1 ]例如 Φ(1,2) 5表示 1 到 2 的最短路徑 1→5→4→1→2 上編號(hào)最大的中間頂點(diǎn)是 5Φ(2,3) 4 表示路徑 2→4→3 的最大中間頂點(diǎn)是 4。利用最終矩陣 Φ (Φ(n)ij) 重寫(xiě)路徑輸出過(guò)程PRINT-ALL-PAIRS-SHORTEST-PATH(Φ, i, j) if i j then print i else if Φ(i, j) -1 // i 與 j 之間無(wú)中間頂點(diǎn) then print no path from i to j exists else PRINT-ALL-PAIRS-SHORTEST-PATH(Φ, i, Φ(i, j)) PRINT-ALL-PAIRS-SHORTEST-PATH(Φ, Φ(i, j), j)注意與基于 Π 的重建方式的區(qū)別Π 記錄j 的直接前驅(qū)重建是從終點(diǎn)向起點(diǎn)回溯而 Φ 記錄最大編號(hào)中間頂點(diǎn)重建是遞歸二分——先把路徑拆成 i→Φ(i,j) 與 Φ(i,j)→j 兩段分別遞歸輸出。這與矩陣鏈乘法問(wèn)題第 15.2 節(jié)中記錄最優(yōu)分割點(diǎn) k的s 表在結(jié)構(gòu)上完全同構(gòu)s[i][j] 保存使 i…j 鏈?zhǔn)匠朔e最優(yōu)的分割點(diǎn)重建時(shí)同樣以 s[i][j] 為界遞歸輸出左右兩半。Φ 就是最短路徑版本的 s 表。9. 習(xí)題 25.2-8O(VE) 時(shí)間計(jì)算有向圖傳遞閉包題目給出一個(gè) O(VE) 時(shí)間的算法計(jì)算有向圖 G (V, E) 的傳遞閉包。方法對(duì)每個(gè)頂點(diǎn)各執(zhí)行一次 DFS/BFS 遍歷。對(duì)每個(gè)源頂點(diǎn) i ∈ V以 i 為根啟動(dòng)一次 DFS或 BFS遍歷過(guò)程中訪問(wèn)到的每個(gè)頂點(diǎn) j都在傳遞閉包矩陣中置 T(i,j) 1i 自身置 1表示長(zhǎng)度為 0 的路徑。復(fù)雜度分析一共 V 個(gè)源點(diǎn)每次遍歷 O(V E)若實(shí)現(xiàn)為在邊集上整體掃描則為 O(E) 級(jí)別的訪問(wèn)量。對(duì)稠密圖V 次遍歷合計(jì) O(V·(VE))但若按鄰接表實(shí)現(xiàn)并對(duì)每個(gè)源點(diǎn)只掃描其可達(dá)邊總時(shí)間可做到 O(V·E)頂點(diǎn)訪問(wèn)開(kāi)銷 O(V2) 可并入或小于 V·E 項(xiàng)按題設(shè)以邊為主。更精確地說(shuō)每次 DFS 訪問(wèn)的頂點(diǎn)與邊都來(lái)自以 i 為根的 DFS 樹(shù)所有 V 棵樹(shù)合計(jì)至多 O(VE) 條邊的訪問(wèn)因此整體O(VE)。該算法不需要任何負(fù)權(quán)假設(shè)、不涉及權(quán)重計(jì)算純粹基于圖的可達(dá)性是傳遞閉包問(wèn)題的經(jīng)典線性級(jí)實(shí)現(xiàn)之一。10. 習(xí)題 25.2-9一般有向圖傳遞閉包與 DAG 算法的歸約題目假設(shè) DAG 的傳遞閉包可在 f(|V|, |E|) 時(shí)間內(nèi)計(jì)算f 對(duì) |V|、|E| 單調(diào)不減。證明一般有向圖 G (V, E) 的傳遞閉包 G* (V, E*) 可在 f(|V|, |E|) O(V E*) 時(shí)間內(nèi)計(jì)算。證明思路文檔給出完整構(gòu)造展開(kāi)如下第 1 步把一般有向圖變成 DAG。任選一個(gè)頂點(diǎn)開(kāi)始 DFS。搜索過(guò)程中如果遇到灰色頂點(diǎn)發(fā)現(xiàn)了一條后向邊/環(huán)說(shuō)明圖中有環(huán)把這條環(huán)邊 (u, v) 記錄下來(lái)并從 E 中刪除。該操作只需一次遍歷復(fù)雜度 O(V E) ≤ O(V E*)因?yàn)?E ? E*環(huán)邊也一定屬于 E*。重復(fù)此過(guò)程直到圖變?yōu)?DAG——由于每輪刪除一條環(huán)邊總輪數(shù)不超過(guò) |E|總開(kāi)銷仍為 O(V E)。第 2 步在 DAG 上運(yùn)行已知算法。對(duì)得到的 DAG 調(diào)用 f(|V|, |E|) 算法得到不完整的傳遞閉包缺少因刪除環(huán)邊而丟失的傳遞關(guān)系。第 3 步補(bǔ)全被刪除的邊。遍歷第 1 步記錄下來(lái)的每條被刪除邊 (u, v)u 的所有可達(dá)點(diǎn) ∪ v 本身 ∪ v 的所有可達(dá)點(diǎn)都應(yīng)在傳遞閉包中標(biāo)記為 u 可達(dá)。由于每條被刪除邊 (u, v) 在 E* 中都存在閉環(huán)邊本身即一條路徑且記錄不重復(fù)遍歷過(guò)程最多把不完整傳遞閉包的每條邊訪問(wèn)一遍、外加這些被刪除的邊開(kāi)銷為 O(E*)其中 E* 是 G 的傳遞閉包邊集。復(fù)雜度匯總f(|V|, |E|)DAG 閉包 O(V E)去環(huán) O(E*)補(bǔ)全≤ f(|V|, |E|) O(V E*)。?該歸約的價(jià)值在于把任意有向圖的傳遞閉包問(wèn)題化歸為DAG 傳遞閉包 線性補(bǔ)償從而 DAG 上任何優(yōu)于 O(VE) 的閉包算法都能直接推廣到一般有向圖。倉(cāng)庫(kù) README.md 將 25.2-3 與 25.2-9 標(biāo)注為待完整驗(yàn)證的難題UNSOLVED本文給出的構(gòu)造性證明即為該兩題的完整推導(dǎo)。11. 倉(cāng)庫(kù)配套實(shí)現(xiàn)速覽從偽代碼到可運(yùn)行 C本倉(cāng)庫(kù)為第 25.2 節(jié)提供了開(kāi)箱即用的配套實(shí)現(xiàn) Floyd_Warshall.cpp其要點(diǎn)如下功能實(shí)現(xiàn)位置說(shuō)明距離矩陣初始化第 24–30 行dist拷貝權(quán)重矩陣對(duì)角線 0不可達(dá)記為 INF99999三重循環(huán)松弛第 32–41 行原地更新dist[i][j] min(dist[i][j], dist[i][k]dist[k][j])即第 5 節(jié) Θ(n2) 空間版本前驅(qū)矩陣維護(hù)第 27–28、37 行初始化Pre[i][j] i1松弛成功時(shí)Pre[i][j] Pre[k][j]對(duì)應(yīng)式 (25.7)距離矩陣輸出第 47–62 行INF 顯示為INF否則按 7 位寬打印前驅(qū)矩陣輸出第 64–78 行同樣以INF顯示無(wú)前驅(qū)路徑重建第 80–92 行findPath(start, end)從終點(diǎn)沿 Pre 回溯到起點(diǎn)并逆序打印編譯運(yùn)行方式Linux/gcd C25-All-Pairs-Shortest-Paths g Floyd_Warshall.cpp -o floyd ./floyd運(yùn)行輸出節(jié)選驗(yàn)證了本文第 2、4 節(jié)的推演Following matrix shows the shortest distances between every pair of vertices 0 1 -3 2 -4 3 0 -4 1 -1 7 4 0 5 3 2 -1 -5 0 -2 8 5 1 6 0 The path : 2 4 1 5其中findPath(2, 5)打印的最短路徑2 → 4 → 1 → 5總權(quán)重 1 (?2) (?4) 0 ?1與最終距離矩陣 D(5) 中的 d(2,5) ?1 完全一致前驅(qū)矩陣的正確性由此得到端到端驗(yàn)證。12. 小結(jié)本節(jié)知識(shí)點(diǎn)一圖流習(xí)題核心知識(shí)點(diǎn)關(guān)鍵結(jié)論25.2-1矩陣推演D(k) 序列每輪只允許中間頂點(diǎn)編號(hào) ≤ k本文給出 5 頂點(diǎn)完整推演并與源碼輸出對(duì)照25.2-2傳遞閉包min→OR、→AND 的布爾半環(huán)替換即可25.2-3前驅(qū)矩陣三步證明 G(π,i)無(wú)環(huán)反證導(dǎo)出負(fù)環(huán)、根樹(shù)唯一前驅(qū)、最短路徑樹(shù)25.2-4空間優(yōu)化去掉上標(biāo)后仍正確關(guān)鍵在 d(i,k)、d(k,j) 當(dāng)輪不被污染空間 Θ(n2)25.2-5等號(hào)變體等號(hào)歸入經(jīng)過(guò) k分支同樣正確25.2-6負(fù)環(huán)檢測(cè)多跑一輪松弛或檢查對(duì)角線 d(i,i) 025.2-7Φ 矩陣Φ(k)ij k經(jīng)過(guò) k 改善或 Φ(k?1)ij重建即遞歸二分與矩陣鏈 s 表同構(gòu)25.2-8O(VE) 閉包每個(gè)頂點(diǎn)各跑一次 DFS25.2-9DAG 歸約去環(huán)刪后向邊→ DAG 閉包 → O(E*) 補(bǔ)全總計(jì) f O(V E*)Floyd-Warshall 之所以是最優(yōu)雅的全源最短路徑算法在于它用最小代價(jià)Θ(n3)/Θ(n2)把動(dòng)態(tài)規(guī)劃、前驅(qū)追蹤、負(fù)環(huán)檢測(cè)與傳遞閉包四個(gè)問(wèn)題統(tǒng)一在同一個(gè)三重循環(huán)之下。掌握本節(jié)習(xí)題的推演與證明即可在面試與工程中熟練應(yīng)用并靈活改造這一核心算法。贊分享文檔教程示例工程【免費(fèi)下載鏈接】CLRS:notebook:Solutions to Introduction to Algorithms項(xiàng)目地址https://gitcode.com/gh_mirrors/cl/CLRS點(diǎn)擊查看免費(fèi)下載相關(guān)推薦CLRS《算法導(dǎo)論》第 4.1 節(jié)習(xí)題精解代入法求解遞歸式的完整實(shí)戰(zhàn)CLRS《算法導(dǎo)論》第 4.1 節(jié)習(xí)題精解代入法求解遞歸式的完整實(shí)戰(zhàn) 本文基于開(kāi)源倉(cāng)庫(kù) gh_mirrors/cl/CLRS Solutions to In文檔教程示例工程算法在計(jì)算中的地位CLRS 第 1 章習(xí)題精解與倉(cāng)庫(kù)實(shí)現(xiàn)印證算法在計(jì)算中的地位CLRS 第 1 章習(xí)題精解與倉(cāng)庫(kù)實(shí)現(xiàn)印證 本篇技術(shù)指南以《算法導(dǎo)論》Introduction to Algorithms, CLRS第文檔教程示例工程CLRS 矩陣鏈乘法深度解析15.2 節(jié)習(xí)題全解與 C 語(yǔ)言實(shí)現(xiàn)驗(yàn)證CLRS 矩陣鏈乘法深度解析15.2 節(jié)習(xí)題全解與 C 語(yǔ)言實(shí)現(xiàn)驗(yàn)證 本篇技術(shù)指南以《算法導(dǎo)論》CLRS第 15 章動(dòng)態(tài)規(guī)劃中矩陣鏈乘法一節(jié)的習(xí)題集 C文檔教程示例工程上一篇Rusted PackFile Manager全面戰(zhàn)爭(zhēng)模組開(kāi)發(fā)的終極解決方案下一篇Rusted PackFile Manager一站式Total War模組開(kāi)發(fā)終極指南創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考