南京網(wǎng)站開發(fā)價(jià)格,wordpress更新配置文件,如何做網(wǎng)站后臺(tái)管理,給我一個(gè)可以在線觀看的懂得目錄 前言 一、前置知識(shí)#xff1a;多源最短路與 Floyd 算法的核心定位 1. 什么是多源最短路#xff1f; 2. 為什么選擇 Floyd 算法#xff1f; 3. 關(guān)鍵前提#xff1a;Floyd 算法的適用條件 4. 核心思想#xff1a;動(dòng)態(tài)規(guī)劃與 “插點(diǎn)法” 空間優(yōu)化#xff1a;從三…目錄前言一、前置知識(shí)多源最短路與 Floyd 算法的核心定位1. 什么是多源最短路2. 為什么選擇 Floyd 算法3. 關(guān)鍵前提Floyd 算法的適用條件4. 核心思想動(dòng)態(tài)規(guī)劃與 “插點(diǎn)法”空間優(yōu)化從三維到二維5. 算法流程總結(jié)二、Floyd 算法的代碼實(shí)現(xiàn)簡潔到極致1. 基礎(chǔ)模板代碼無向圖2. 有向圖的修改3. 關(guān)鍵細(xì)節(jié)說明三、模板題實(shí)戰(zhàn)洛谷 B3647 【模板】Floyd題目鏈接題目描述輸入描述輸出描述示例輸入示例輸出解題思路完整 C 代碼代碼解釋四、基礎(chǔ)應(yīng)用洛谷 P2910 Clear And Present Danger題目鏈接題目描述輸入描述示例輸入示例輸出解題思路完整 C 代碼代碼解釋五、進(jìn)階實(shí)戰(zhàn)洛谷 P1119 災(zāi)后重建題目鏈接題目描述輸入描述示例輸入示例輸出解題思路關(guān)鍵觀察算法設(shè)計(jì)為什么這樣可行完整 C 代碼代碼解釋六、拓展應(yīng)用洛谷 P6175 無向圖的最小環(huán)問題題目鏈接題目描述輸入描述示例輸入示例輸出解題思路核心觀察算法設(shè)計(jì)關(guān)鍵細(xì)節(jié)完整 C 代碼代碼解釋七、Floyd 算法的優(yōu)化與注意事項(xiàng)1. 空間優(yōu)化2. 避免溢出3. 處理重邊和自環(huán)4. 負(fù)環(huán)的檢測(cè)總結(jié)前言在圖論的應(yīng)用場(chǎng)景中我們常常會(huì)遇到這樣的需求地圖應(yīng)用中查詢?nèi)我鈨蓚€(gè)城市間的最短車程、網(wǎng)絡(luò)拓?fù)渲杏?jì)算任意兩臺(tái)設(shè)備間的最優(yōu)傳輸路徑、物流規(guī)劃中確定任意兩個(gè)倉庫間的最低運(yùn)輸成本…… 這些問題的核心都是多源最短路—— 即求出圖中每一對(duì)頂點(diǎn)之間的最短路徑。單源最短路解決的是 “從一個(gè)起點(diǎn)到所有其他點(diǎn)” 的路徑問題而多源最短路則需要覆蓋 “所有點(diǎn)到所有點(diǎn)” 的全量路徑。今天這篇文章我會(huì)聚焦多源最短路的經(jīng)典解法 ——Floyd-Warshall 算法簡稱 Floyd 算法從原理剖析、代碼實(shí)現(xiàn)到實(shí)戰(zhàn)例題帶你徹底掌握這一 “通吃所有點(diǎn)對(duì)” 的強(qiáng)大算法。不僅如此我還會(huì)分享 Floyd 算法的核心拓展應(yīng)用如無向圖最小環(huán)問題、動(dòng)態(tài)加點(diǎn)的最短路徑查詢結(jié)合洛谷經(jīng)典例題讓你從 “理解算法” 到 “靈活運(yùn)用”真正吃透多源最短路問題下面就讓我們正式開始吧一、前置知識(shí)多源最短路與 Floyd 算法的核心定位在正式講解算法之前我們先明確幾個(gè)關(guān)鍵概念幫你建立對(duì)多源最短路的清晰認(rèn)知1. 什么是多源最短路多源最短路的定義很簡單給定一個(gè)帶權(quán)圖有向或無向邊權(quán)可正可負(fù)但不能存在負(fù)環(huán)否則部分點(diǎn)對(duì)的最短路徑不存在求出所有頂點(diǎn)對(duì) (i, j)之間的最短路徑長度i 到 j 的最短路徑以及 j 到 i 的最短路徑若圖為有向圖則可能不同。2. 為什么選擇 Floyd 算法解決多源最短路其實(shí)有兩種思路思路 1對(duì)每個(gè)頂點(diǎn)都跑一遍單源最短路算法如 Dijkstra 或 SPFA。若圖中有 n 個(gè)頂點(diǎn)時(shí)間復(fù)雜度為 O (n×(m log n))堆優(yōu)化 Dijkstra適用于稀疏圖。思路 2使用 Floyd 算法時(shí)間復(fù)雜度為 O (n3)適用于稠密圖n 較小如 n≤200。Floyd 算法的核心優(yōu)勢(shì)在于實(shí)現(xiàn)簡單、代碼簡潔僅需三層循環(huán)即可完成無需復(fù)雜的數(shù)據(jù)結(jié)構(gòu)支持。對(duì)于 n≤200 的場(chǎng)景O (n3) 的時(shí)間復(fù)雜度完全可接受20038e6計(jì)算機(jī)可瞬間處理因此成為多源最短路的首選算法。3. 關(guān)鍵前提Floyd 算法的適用條件Floyd 算法雖然強(qiáng)大但有一個(gè)重要前提圖中不能存在負(fù)環(huán)。因?yàn)槿绻嬖谪?fù)環(huán)那么經(jīng)過負(fù)環(huán)的點(diǎn)對(duì)之間的路徑長度可以無限減小不存在最短路徑。但要注意Floyd 算法支持負(fù)權(quán)邊只要沒有負(fù)環(huán)。例如圖中存在邊權(quán)為 - 2、-3 的邊只要沒有形成回路的邊權(quán)和為負(fù)就可以正常計(jì)算。4. 核心思想動(dòng)態(tài)規(guī)劃與 “插點(diǎn)法”Floyd 算法的本質(zhì)是動(dòng)態(tài)規(guī)劃其核心思想可以概括為 “插點(diǎn)法”—— 通過不斷在兩個(gè)頂點(diǎn)之間插入新的頂點(diǎn)更新這兩個(gè)頂點(diǎn)之間的最短路徑。我們用一個(gè)三維數(shù)組f[k][i][j]來表示動(dòng)態(tài)規(guī)劃的狀態(tài)狀態(tài)定義f[k][i][j]表示 “僅允許經(jīng)過頂點(diǎn) 1~k 作為中轉(zhuǎn)點(diǎn)時(shí)頂點(diǎn) i 到頂點(diǎn) j 的最短路徑長度”?；谶@個(gè)狀態(tài)定義我們可以得到狀態(tài)轉(zhuǎn)移方程當(dāng)不使用頂點(diǎn) k 作為中轉(zhuǎn)點(diǎn)時(shí)f[k][i][j] f[k-1][i][j]最短路徑還是原來的路徑當(dāng)使用頂點(diǎn) k 作為中轉(zhuǎn)點(diǎn)時(shí)f[k][i][j] min(f[k-1][i][k] f[k-1][k][j], f[k-1][i][j])比較 “直接從 i 到 j” 和 “i 經(jīng)過 k 到 j” 的路徑長度取較小值?？臻g優(yōu)化從三維到二維觀察狀態(tài)轉(zhuǎn)移方程可以發(fā)現(xiàn)f[k][i][j]只依賴于f[k-1][...]上一層的狀態(tài)因此我們可以將三維數(shù)組優(yōu)化為二維數(shù)組f[i][j]直接在原數(shù)組上進(jìn)行更新。優(yōu)化后的狀態(tài)轉(zhuǎn)移方程為f[i][j] min(f[i][j], f[i][k] f[k][j])這里的k是 “當(dāng)前允許使用的中轉(zhuǎn)頂點(diǎn)”因此循環(huán)順序必須是先枚舉 k再枚舉 i 和 j—— 這是 Floyd 算法的關(guān)鍵細(xì)節(jié)也是最容易出錯(cuò)的地方5. 算法流程總結(jié)Floyd 算法的流程非常簡潔總共分為 3 步初始化創(chuàng)建二維數(shù)組ff[i][j]表示頂點(diǎn) i 到頂點(diǎn) j 的初始距離。若 i j則f[i][j] 0自己到自己的距離為 0若 i 和 j 之間有直接邊權(quán)值為 w則f[i][j] w若 i 和 j 之間沒有直接邊則f[i][j] INFINF 表示無窮大代表初始時(shí)不可達(dá)。插點(diǎn)更新枚舉所有可能的中轉(zhuǎn)頂點(diǎn) k1~n然后枚舉所有頂點(diǎn)對(duì) (i, j)用f[i][k] f[k][j]更新f[i][j]。結(jié)果輸出f[i][j]即為頂點(diǎn) i 到頂點(diǎn) j 的最短路徑長度若仍為 INF則表示不可達(dá)。二、Floyd 算法的代碼實(shí)現(xiàn)簡潔到極致基于上述思路我們可以寫出 Floyd 算法的 C 代碼。代碼非常簡潔核心僅需三層循環(huán)適合記憶和默寫。1. 基礎(chǔ)模板代碼無向圖#include iostream #include cstring using namespace std; const int N 110; // 頂點(diǎn)數(shù)上限根據(jù)題目調(diào)整 const int INF 0x3f3f3f3f; // 表示無窮大注意避免溢出 int n, m; int f[N][N]; // f[i][j]i到j(luò)的最短路徑長度 void floyd() { // 枚舉中轉(zhuǎn)頂點(diǎn)k for (int k 1; k n; k) { // 枚舉所有頂點(diǎn)對(duì)(i, j) for (int i 1; i n; i) { for (int j 1; j n; j) { // 狀態(tài)轉(zhuǎn)移用k更新i到j(luò)的最短路徑 f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } } int main() { cin n m; // 1. 初始化f數(shù)組 memset(f, 0x3f, sizeof f); // 所有邊初始化為無窮大 for (int i 1; i n; i) { f[i][i] 0; // 自己到自己的距離為0 } // 2. 讀入邊的信息無向圖雙向賦值 for (int i 0; i m; i) { int u, v, w; cin u v w; // 若存在重邊取權(quán)值最小的邊 f[u][v] min(f[u][v], w); f[v][u] min(f[v][u], w); } // 3. 執(zhí)行Floyd算法 floyd(); // 4. 輸出所有點(diǎn)對(duì)的最短路徑 for (int i 1; i n; i) { for (int j 1; j n; j) { if (f[i][j] INF) { cout INF ; // 不可達(dá) } else { cout f[i][j] ; } } cout endl; } return 0; }2. 有向圖的修改如果圖是有向圖只需修改邊的初始化部分 —— 僅需賦值f[u][v] min(f[u][v], w)無需賦值f[v][u]因?yàn)橛邢蜻叺姆较蚴菃蜗虻?。修改后的邊初始化代碼// 讀入有向邊u→v權(quán)值w for (int i 0; i m; i) { int u, v, w; cin u v w; f[u][v] min(f[u][v], w); // 僅單向賦值 }3. 關(guān)鍵細(xì)節(jié)說明無窮大的選擇使用0x3f3f3f3f作為無窮大原因是它是一個(gè)較大的數(shù)約 1e9不會(huì)被正常的邊權(quán)值超過兩個(gè)0x3f3f3f3f相加不會(huì)溢出0x3f3f3f3f * 2 0x7ffffffe小于 int 的最大值0x7fffffff。重邊處理如果圖中存在重邊多個(gè)邊連接同一對(duì)頂點(diǎn)我們?nèi)?quán)值最小的邊因此用min(f[u][v], w)賦值。循環(huán)順序必須先枚舉中轉(zhuǎn)頂點(diǎn) k再枚舉 i 和 j如果順序錯(cuò)誤會(huì)導(dǎo)致部分路徑無法正確更新。三、模板題實(shí)戰(zhàn)洛谷 B3647 【模板】Floyd題目鏈接B3647 【模板】Floyd題目描述給出一張由n個(gè)點(diǎn)m條邊組成的無向圖求出所有點(diǎn)對(duì)(i, j)之間的最短路徑。輸入描述第一行兩個(gè)整數(shù)n、m分別表示頂點(diǎn)數(shù)和邊數(shù)接下來m行每行三個(gè)整數(shù)u、v、w表示頂點(diǎn)u和v之間有一條權(quán)值為w的無向邊。輸出描述輸出n行每行n個(gè)整數(shù)第i行第j個(gè)整數(shù)表示頂點(diǎn)i到j(luò)的最短路徑長度。示例輸入4 4 1 2 1 2 3 1 3 4 1 4 1 1示例輸出0 1 2 1 1 0 1 2 2 1 0 1 1 2 1 0解題思路這是 Floyd 算法的基礎(chǔ)模板題無向圖可看作雙向有向圖因此讀入邊時(shí)需同時(shí)更新f[u][v]和f[v][u]。直接套用 Floyd 算法框架即可。完整 C 代碼#include iostream #include cstring using namespace std; const int N 110; const int INF 0x3f3f3f3f; int n, m; int f[N][N]; int main() { // 初始化f數(shù)組 memset(f, 0x3f, sizeof f); for (int i 1; i N; i) { f[i][i] 0; } // 讀入數(shù)據(jù) cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; // 無向邊雙向更新保留最小權(quán)值避免重邊 f[u][v] min(f[u][v], w); f[v][u] min(f[v][u], w); } // Floyd核心算法 for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { if (f[i][k] ! INF f[k][j] ! INF) { f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } } // 輸出結(jié)果 for (int i 1; i n; i) { for (int j 1; j n; j) { cout f[i][j] ; } cout endl; } return 0; }代碼解釋初始化時(shí)f[i][i] 0其余為INF無向邊需雙向更新避免重邊影響取最小權(quán)值三層循環(huán)嚴(yán)格按照k → i → j的順序確保每個(gè)中間頂點(diǎn)都能正確更新路徑輸出時(shí)直接打印f[i][j]即為i到j(luò)的最短路徑長度。四、基礎(chǔ)應(yīng)用洛谷 P2910 Clear And Present Danger題目鏈接P2910 [USACO08OPEN] Clear And Present Danger S題目描述農(nóng)夫約翰駕駛小艇在海上航行海上有N個(gè)島嶼編號(hào) 1~N。約翰需要按照藏寶圖上的序列A?, A?, ..., A?依次經(jīng)過這些島嶼從A?出發(fā)最后到A?求經(jīng)過的航線危險(xiǎn)指數(shù)之和的最小值。危險(xiǎn)指數(shù)D[i][j]表示島嶼i到j(luò)的直接航線危險(xiǎn)指數(shù)題目已給出所有D[i][j]。輸入描述第一行兩個(gè)整數(shù)N、M分別表示島嶼數(shù)和必須經(jīng)過的島嶼序列長度接下來M行每行一個(gè)整數(shù)A?表示必須經(jīng)過的第i個(gè)島嶼接下來N行每行N個(gè)整數(shù)第i行第j個(gè)整數(shù)表示D[i][j]D[i][i] 0。示例輸入3 4 1 2 1 3 0 5 1 5 0 2 1 2 0示例輸出7解題思路題目給出的D[i][j]是直接航線的危險(xiǎn)指數(shù)但可能存在經(jīng)過其他島嶼的更短路徑危險(xiǎn)指數(shù)更小因此需要先通過 Floyd 算法求出所有島嶼對(duì)之間的最短危險(xiǎn)指數(shù)即任意兩個(gè)島嶼之間的最優(yōu)路徑然后按照序列A? → A? → ... → A?累加相鄰島嶼的最短危險(xiǎn)指數(shù)之和即為答案。完整 C 代碼#include iostream #include cstring typedef long long LL; // 防止結(jié)果溢出 using namespace std; const int N 110; const int INF 0x3f3f3f3f; int n, m; int f[N][N]; int a[10010]; // 存儲(chǔ)必須經(jīng)過的島嶼序列M最大為1e4 int main() { // 讀入島嶼數(shù)和序列長度 cin n m; // 讀入必須經(jīng)過的島嶼序列 for (int i 1; i m; i) { cin a[i]; } // 讀入初始危險(xiǎn)指數(shù)矩陣D[i][j]并初始化f數(shù)組 for (int i 1; i n; i) { for (int j 1; j n; j) { cin f[i][j]; } } // Floyd算法求所有島嶼對(duì)的最短危險(xiǎn)指數(shù) for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { if (f[i][k] ! INF f[k][j] ! INF) { f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } } // 累加序列中相鄰島嶼的最短危險(xiǎn)指數(shù)之和 LL res 0; for (int i 2; i m; i) { int u a[i-1], v a[i]; res f[u][v]; } // 輸出結(jié)果 cout res endl; return 0; }代碼解釋由于M最大為 1e4N最大為 100f[i][j]最大為 1e5累加和可能超過 int 范圍因此用long long存儲(chǔ)結(jié)果初始時(shí)f[i][j]直接賦值為題目給出的D[i][j]無需額外初始化題目已保證D[i][i] 0累加過程中直接使用 Floyd 更新后的f[u][v]u和v為序列中相鄰島嶼確保每一段都是最優(yōu)路徑。五、進(jìn)階實(shí)戰(zhàn)洛谷 P1119 災(zāi)后重建題目鏈接P1119 災(zāi)后重建題目描述B 地區(qū)有N個(gè)村莊編號(hào) 0~N-1M條雙向公路。每個(gè)村莊i有一個(gè)重建完成時(shí)間t[i]t[i]為 0 表示初始即可通車重建完成當(dāng)天即可通車。有Q個(gè)詢問(x, y, t)詢問在第t天村莊x到y(tǒng)的最短路徑長度路徑必須經(jīng)過已重建完成的村莊。若無法到達(dá)如x或y未重建、無路徑輸出-1。輸入描述第一行兩個(gè)整數(shù)N、M表示村莊數(shù)和公路數(shù)第二行N個(gè)非負(fù)整數(shù)t[0], t[1], ..., t[N-1]表示每個(gè)村莊的重建時(shí)間保證t非遞減接下來M行每行三個(gè)整數(shù)i、j、w表示村莊i和j之間有一條長度為w的公路接下來一行整數(shù)Q表示詢問數(shù)接下來Q行每行三個(gè)整數(shù)x、y、t表示詢問保證t非遞減。示例輸入4 5 1 2 3 4 0 2 1 2 3 1 3 1 2 2 1 4 0 3 5 4 2 0 2 0 1 2 0 1 3 0 1 4示例輸出-1 -1 5 4解題思路這道題是 Floyd 算法的經(jīng)典進(jìn)階應(yīng)用核心在于理解 “重建時(shí)間” 對(duì)路徑的限制 —— 只有重建完成的村莊才能作為中間頂點(diǎn)或路徑上的頂點(diǎn)。關(guān)鍵觀察村莊的重建時(shí)間t是非遞減的t[0] ≤ t[1] ≤ ... ≤ t[N-1]詢問的時(shí)間t也是非遞減的Floyd 算法的 “插點(diǎn)法” 本質(zhì)是依次將頂點(diǎn)作為中間頂點(diǎn)加入更新路徑。這與 “村莊按重建時(shí)間依次通車” 的過程完全契合算法設(shè)計(jì)初始化 Floyd 數(shù)組f公路初始長度為給定w無公路為INFf[i][i] 0維護(hù)一個(gè)指針pos表示當(dāng)前已重建完成的村莊初始pos 0對(duì)于每個(gè)詢問(x, y, t)a. 先將所有重建時(shí)間≤ t的村莊t[pos] ≤ t作為中間頂點(diǎn)加入 Floyd 算法更新路徑因?yàn)檫@些村莊已通車可作為中轉(zhuǎn)b. 檢查x和y是否已重建t[x] ≤ t且t[y] ≤ tc. 若已重建且f[x][y] ! INF輸出f[x][y]否則輸出-1。為什么這樣可行由于村莊重建時(shí)間和詢問時(shí)間都是非遞減的一旦某個(gè)村莊被加入作為中間頂點(diǎn)后續(xù)的詢問都可以使用它無需重復(fù)處理每次詢問前只需要處理新增的已重建村莊避免了重復(fù)計(jì)算時(shí)間復(fù)雜度優(yōu)化為O(Q N2 M)因?yàn)槊總€(gè)村莊最多被處理一次每次處理O(N2)。完整 C 代碼#include iostream #include cstring using namespace std; const int N 210; const int INF 0x3f3f3f3f; int n, m, q; int t[N]; // 每個(gè)村莊的重建時(shí)間 int f[N][N]; // Floyd數(shù)組 // 加入村莊k作為中間頂點(diǎn)更新所有路徑 void floyd(int k) { for (int i 0; i n; i) { for (int j 0; j n; j) { if (f[i][k] ! INF f[k][j] ! INF) { f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } } int main() { // 初始化Floyd數(shù)組 memset(f, 0x3f, sizeof f); for (int i 0; i N; i) { f[i][i] 0; } // 讀入村莊數(shù)和公路數(shù) cin n m; // 讀入每個(gè)村莊的重建時(shí)間 for (int i 0; i n; i) { cin t[i]; } // 讀入公路信息 for (int i 0; i m; i) { int u, v, w; cin u v w; f[u][v] min(f[u][v], w); f[v][u] min(f[v][u], w); // 無向公路雙向更新 } // 讀入詢問數(shù) cin q; int pos 0; // 當(dāng)前已處理的最后一個(gè)村莊已重建完成 while (q--) { int x, y, time; cin x y time; // 將所有重建時(shí)間≤當(dāng)前詢問時(shí)間的村莊加入Floyd while (pos n t[pos] time) { floyd(pos); pos; } // 檢查x和y是否已重建且存在路徑 if (t[x] time || t[y] time || f[x][y] INF) { cout -1 endl; } else { cout f[x][y] endl; } } return 0; }代碼解釋村莊編號(hào)從 0 開始與題目一致因此數(shù)組初始化和循環(huán)均從 0 開始floyd(k)函數(shù)的作用是將村莊k作為中間頂點(diǎn)更新所有頂點(diǎn)對(duì)的最短路徑指針pos的作用是 “懶加載” 已重建的村莊避免重復(fù)處理優(yōu)化時(shí)間復(fù)雜度詢問處理時(shí)先確保所有已重建的村莊都被作為中間頂點(diǎn)加入再判斷路徑是否存在。六、拓展應(yīng)用洛谷 P6175 無向圖的最小環(huán)問題題目鏈接P6175 無向圖的最小環(huán)問題題目描述給定一張無向圖求圖中一個(gè)至少包含 3 個(gè)頂點(diǎn)的環(huán)使得環(huán)上所有邊的權(quán)值之和最小即最小環(huán)。若無環(huán)輸出No solution.。輸入描述第一行兩個(gè)整數(shù)n、m表示頂點(diǎn)數(shù)和邊數(shù)接下來m行每行三個(gè)整數(shù)u、v、d表示頂點(diǎn)u和v之間有一條權(quán)值為d的無向邊。示例輸入5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20示例輸出61解題思路最小環(huán)問題是多源最短路的經(jīng)典拓展Floyd 算法可以巧妙地解決這個(gè)問題。核心觀察無向圖中的最小環(huán)必然可以表示為i → ... → k → j → i其中k是環(huán)中編號(hào)最大的頂點(diǎn)i和j是環(huán)中與k直接相連的兩個(gè)頂點(diǎn)i → ... → j的路徑中不包含k因?yàn)閗是最大編號(hào)頂點(diǎn)因此這條路徑的最短長度就是f[k-1][i][j]只允許經(jīng)過頂點(diǎn) 1~k-1 時(shí)的最短路徑。因此最小環(huán)的長度可以表示為f[k-1][i][j] w[i][k] w[k][j]其中w[i][k]是i到k的直接邊權(quán)w[k][j]是k到j(luò)的直接邊權(quán)。算法設(shè)計(jì)初始化 Floyd 數(shù)組f和原始邊權(quán)數(shù)組ww[i][j]存儲(chǔ)i到j(luò)的直接邊權(quán)枚舉中間頂點(diǎn)k從 1 到 na. 在更新f[k][i][j]之前先枚舉所有i k、j k、i ! j計(jì)算f[k-1][i][j] w[i][k] w[k][j]并更新最小環(huán)長度b. 然后正常執(zhí)行 Floyd 的狀態(tài)轉(zhuǎn)移更新f[k][i][j]枚舉結(jié)束后若最小環(huán)長度仍為無窮大輸出No solution.否則輸出最小環(huán)長度。關(guān)鍵細(xì)節(jié)必須在更新f[k][i][j]之前計(jì)算最小環(huán)因?yàn)榇藭r(shí)f[i][j]仍保持著“只允許經(jīng)過 1~k-1”的狀態(tài)原始邊權(quán)數(shù)組w需要單獨(dú)保存不能被 Floyd 更新覆蓋因?yàn)閣[i][k]是i到k的直接邊權(quán)而非最短路徑。完整 C 代碼#include iostream #include cstring using namespace std; const int N 110; const int INF 1e8; // 無窮大避免溢出 int n, m; int f[N][N]; // Floyd數(shù)組存儲(chǔ)最短路徑 int w[N][N]; // 原始邊權(quán)數(shù)組存儲(chǔ)直接邊權(quán) int min_cycle INF; // 最小環(huán)長度 int main() { // 初始化f和w數(shù)組 for (int i 1; i N; i) { for (int j 1; j N; j) { f[i][j] w[i][j] INF; } f[i][i] w[i][i] 0; } // 讀入頂點(diǎn)數(shù)和邊數(shù) cin n m; for (int i 0; i m; i) { int u, v, d; cin u v d; // 無向邊雙向更新保留最小邊權(quán)避免重邊 w[u][v] w[v][u] min(w[u][v], d); f[u][v] f[v][u] min(f[u][v], d); } // Floyd算法求最短路徑并同時(shí)找最小環(huán) for (int k 1; k n; k) { // 步驟1找包含k的最小環(huán)k是環(huán)中最大編號(hào)頂點(diǎn) for (int i 1; i k; i) { for (int j i 1; j k; j) { // 環(huán)的長度 i到j(luò)的最短路徑不經(jīng)過k i到k的直接邊 k到j(luò)的直接邊 if (f[i][j] ! INF w[i][k] ! INF w[k][j] ! INF) { min_cycle min(min_cycle, f[i][j] w[i][k] w[k][j]); } } } // 步驟2正常更新Floyd數(shù)組插入k作為中間頂點(diǎn) for (int i 1; i n; i) { for (int j 1; j n; j) { if (f[i][k] ! INF f[k][j] ! INF) { f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } } // 輸出結(jié)果 if (min_cycle INF) { cout No solution. endl; } else { cout min_cycle endl; } return 0; }代碼解釋單獨(dú)維護(hù)w數(shù)組存儲(chǔ)原始邊權(quán)避免被 Floyd 更新覆蓋枚舉k時(shí)先找包含k的最小環(huán)i k、j k確保k是環(huán)中最大編號(hào)頂點(diǎn)再更新 Floyd 數(shù)組最小環(huán)的長度是i→j的最短路徑不經(jīng)過k加上i→k和k→j的直接邊權(quán)確保環(huán)的完整性和最小性。七、Floyd 算法的優(yōu)化與注意事項(xiàng)1. 空間優(yōu)化Floyd 算法的空間復(fù)雜度是O(n2)對(duì)于n1000的場(chǎng)景n21e6內(nèi)存占用約 4MBint 類型完全可以接受但對(duì)于n1e4n21e8內(nèi)存占用約 400MB會(huì)超出內(nèi)存限制。此時(shí)可以考慮若只需查詢部分頂點(diǎn)對(duì)的最短路徑可使用多源 Dijkstra對(duì)每個(gè)頂點(diǎn)跑一次 Dijkstra對(duì)于稀疏圖多源 Dijkstra 的時(shí)間復(fù)雜度O(n m log n)可能優(yōu)于 Floyd 的O(n3)。2. 避免溢出無窮大INF的取值要合適不能太大否則INF INF會(huì)溢出也不能太小否則會(huì)與實(shí)際邊權(quán)沖突。通常取0x3f3f3f3f約 1e9因?yàn)?x3f3f3f3f 0x3f3f3f3f 2e9小于 int 的最大值2^31-12147483647若邊權(quán)較大或頂點(diǎn)數(shù)較多需用long long存儲(chǔ)f[i][j]避免累加和溢出。3. 處理重邊和自環(huán)重邊保留權(quán)值最小的邊如w[u][v] min(w[u][v], d)自環(huán)由于f[i][i] 0自環(huán)的邊權(quán)不會(huì)影響最短路徑因?yàn)閕→i的最短路徑長度為 0因此可以忽略自環(huán)或在初始化時(shí)不處理自環(huán)。4. 負(fù)環(huán)的檢測(cè)Floyd 算法本身無法直接檢測(cè)負(fù)環(huán)但可以通過以下方法判斷運(yùn)行 Floyd 算法后若存在f[i][i] 0則說明頂點(diǎn)i在一個(gè)負(fù)環(huán)上因?yàn)樽约旱阶约旱淖疃搪窂介L度為負(fù)數(shù)存在負(fù)環(huán)若只需檢測(cè)是否存在負(fù)環(huán)建議使用 Bellman-Ford 或 SPFA 算法效率更高?？偨Y(jié)Floyd 算法是多源最短路的核心算法代碼簡潔、思想巧妙雖然時(shí)間復(fù)雜度為O(n3)但在頂點(diǎn)數(shù)較小的場(chǎng)景n ≤ 200中效率很高且能處理有向圖、無向圖、帶權(quán)圖非負(fù)權(quán)或負(fù)權(quán)無負(fù)環(huán)等多種情況。Floyd 算法雖然簡單但蘊(yùn)含的動(dòng)態(tài)規(guī)劃思想和 “插點(diǎn)法” 技巧值得深入思考。希望通過本文的學(xué)習(xí)你能徹底掌握多源最短路問題并能靈活應(yīng)對(duì)各類實(shí)戰(zhàn)場(chǎng)景如果有任何疑問或問題歡迎在評(píng)論區(qū)交流討論