Floyd 算法是一種用于尋找加權圖中所有頂點對之間最短路徑的經典算法，它能夠處理負權邊，但不能處理負權環。即如果邊權有負數，切負權邊與其他邊構成了環就不能用該算法。該算法的時間復雜度為?\(O(V^3)\)，其中?V?是圖中頂點的數量。

算法核心思想

Floyd 算法的核心思想是動態規劃。它通過逐步引入中間頂點來不斷更新任意兩點之間的最短路徑。具體來說：

1. 初始化：假設圖用鄰接矩陣?dist[][]?表示，其中?dist[i][j]?表示頂點?i?到頂點?j?的初始距離。如果?i?和?j?之間沒有直接邊，則?dist[i][j]?為無窮大（通常用一個很大的數表示）。
2. 動態規劃更新：對于每一個中間頂點?k，檢查是否可以通過?k?作為中間點來縮短從?i?到?j?的路徑。即更新條件為： \(\text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][k] + \text{dist}[k][j])\)
3. 重復步驟 2：依次考慮所有中間頂點?k?從?0?到?V-1，最終得到所有頂點對之間的最短路徑。

例題

題目描述：所有城市間的最短路徑

有?n?個城市和?m?條道路，每條道路連接兩個城市并具有一定的長度。請計算任意兩個城市之間的最短路徑長度。如果兩個城市之間無法到達，則輸出?-1。

輸入格式：

• 第一行包含兩個整數?n?和?m（1 ≤ n ≤ 200，0 ≤ m ≤ n(n-1)/2）。
• 接下來的?m?行，每行包含三個整數?u,?v,?w，表示城市?u?到城市?v?有一條長度為?w?的雙向道路（1 ≤ u, v ≤ n，1 ≤ w ≤ 1000）。

輸出格式：

• 輸出一個?n × n?的矩陣，其中第?i?行第?j?列的元素表示城市?i?到城市?j?的最短路徑長度。如果無法到達，輸出?-1。

樣例：

輸入

4 4
1 2 1
2 3 2
3 4 3
1 4 10

輸出

0 1 3 6
1 0 2 5
3 2 0 3
6 5 3 0

答案?

#include <iostream>
#include<cstring>
#include <algorithm>
using namespace std;const int INF = 0x3f3f3f3f;
int n,m;
int graph[205][205];
int main() {cin>>n>>m;//距離初始化為最大值memset(graph,INF,sizeof(graph));//自己到自己的距離為0for (int i = 1; i <= n; i++) {graph[i][i] = 0;}int u,v,w;for(int i=0;i<m;i++){cin>>u>>v>>w;graph[u][v]=min(graph[u][v],w);graph[v][u]=min(graph[v][u],w);}//floyed算法for(int k=1;k<=n;k++){  //中樞點for(int i=1;i<=n;i++){  //起點for(int j=1;j<=n;j++){  //終點if(graph[i][k]+graph[k][j]<graph[i][j]){graph[i][j]=graph[i][k]+graph[k][j];}}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(graph[i][j]==INF){cout<<-1<<" ";}else{cout<<graph[i][j]<<" ";}}cout<<endl;}return 0;
}

應用場景

• 計算圖中所有頂點對之間的最短路徑。
• 檢測圖中是否存在負權環。
• 計算傳遞閉包（Transitive Closure）。