問題

求解任意兩點間最短路問題也叫多源最短路徑問題。

可解決途徑

一種方法時把圖中每個點當做源點重復算n次Dijkstra 算法（Dijkstra是求單源最短路徑的算法），時間復雜度O（n^3），據說可以優(yōu)化成O（ n^2 * logn）。
另一種方法時最經典的算法Floyd算法，時間復雜度也是O（n^3），但是關鍵代碼只有5行，適合時間要求不苛刻的時候編寫。

Floyd算法基本思想

Floyd算法本質上是一個動態(tài)規(guī)劃算法。對于每個頂點k，枚舉其他兩個頂點i和j，若i和j之間的距離大于i到k加上k到j的距離，那么更新i到j之間的距離。

【注】Floyd算法允許圖中有帶負權值的邊，但不允許有包含帶負權值的邊組成的回路。（這句話摘自書上，本人并未深刻理解，若有大佬理解，望指教一二）

基本操作

d[k][i][j] 表示 頂點i 經過頂點k 到頂點j 的最短路徑長度。

分兩種情況討論：

經過頂點k, d[k][i][j] = d[k-1][i][j]。 即等于只用前k-1個頂點時的最短路徑

不經過頂點k, d[k][i][j] = d[k-1][i][k] + d[k-1][k][j]。 即等于i離k的最路路徑+k離j的最短路徑。

可以得到遞推式 d[k][i][j] = min( d[k-1][i][j] , d[k-1][i][k] + d[k-1][s][k] );

還可優(yōu)化

由于第k層只與k-1層相關，也可以用二維表示：
（圖片）
（本圖來自知乎，放在此處侵刪）
d[i][j] = min( d[i][j] , d[i][k] + d[k][j] );

精簡版算法模板：

#include <bits\stdc++.h> using namespace std; #define INF 2147483647 #define MAX_V 1000 #define MAX_E 2000 int d[MAX_V][MAX_V]; // d[u][v]表示邊u->v的距離（不存在時設為INF，d[i][i] = 0） int V; // 頂點數 void warshall_floyd(){for(int k = 0;k < V; k++){for(int i = 0;i < V; i++){for(int j = 0;j < V; j++){if(i != j && i != k && j != k)if(d[i][k] != INF && d[k][j] != INF) //INF與正數相加會溢出d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}} } int main(){ } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【算法】Floyd-Warshall算法（任意两点间的最短路问题）（判断负圈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。