目錄

一、概念

二、思路

三、代碼

---

一、概念

在前面的學(xué)習(xí)中，我們已經(jīng)接觸了Dijkstra、Bellman-Ford等單源最短路徑算法。但首先我們要知道何為單源最短路徑，何為多源最短路徑

• 單源最短路徑：從圖中選取一點(diǎn)，求這個(gè)點(diǎn)到圖中其他節(jié)點(diǎn)的最短路徑
• 多源最短路徑：從圖中任選兩個(gè)節(jié)點(diǎn)，我們都能知道這兩點(diǎn)間的最短路徑

Floyd多源最短路徑算法可用于求圖中任意兩點(diǎn)間的最短路徑長，其核心思路在于依次將每個(gè)節(jié)點(diǎn)作為路徑的中間點(diǎn)來更新其他任意兩點(diǎn)的較優(yōu)解，最后得到全局最優(yōu)解

---

二、思路

1.首先我們需要一個(gè)圖，和二維數(shù)組g、path

其中：

• g用于存儲從i到j(luò)的最短路徑長度
• path用于存儲從i到j(luò)的最短路徑的終點(diǎn) 的 前繼節(jié)點(diǎn)

例如初始時(shí)，從1到2的最短路徑就是權(quán)重為6的邊，其終點(diǎn)為2，而對于這條路徑而言2的前繼節(jié)點(diǎn)為1，因此path[1][2] = 1

g(0)和path(0)意為矩陣g和path的初始態(tài)。因?yàn)槌跏紩r(shí)兩個(gè)節(jié)點(diǎn)之間的最短路徑就是他們之間的邊，因此我們在初始化這兩個(gè)數(shù)組時(shí)，只需要按照樣例輸入的邊填寫矩陣g即可

若從i到j(luò)之間沒有邊，則填最大值即可，例如g[3][2] = MAX，因?yàn)闆]有從3指向2的邊

而矩陣path在初始化時(shí)按照上面的規(guī)則初始化即可，例如初始從3到1的最短路徑就是3->1，終點(diǎn)為1，前繼節(jié)點(diǎn)為3，因此path[3][1] = 3

2. 從1號節(jié)點(diǎn)開始，將每個(gè)節(jié)點(diǎn)作為任意兩個(gè)節(jié)點(diǎn)的最短路徑的中間點(diǎn)

有的人聽到這里可能已經(jīng)懵了，我們跟著圖慢慢走

此時(shí)g(0)、path(0)變?yōu)間(1)和path(1)，代表接下來要更新 i->1->j 的最短路徑

但是我們并不需要將矩陣g和矩陣path中的所有值都更新，例如g[1][2]，判斷1->1->2的路徑是否比1->2的最短路徑更短是不具有價(jià)值的。兩個(gè)矩陣中，如果行標(biāo)和中間節(jié)點(diǎn)一樣、列標(biāo)和中間節(jié)點(diǎn)一樣或者行標(biāo)和列標(biāo)一樣的話，我們直接跳過即可

因此，只有2->1->3的情況，和3->1->2的情況需要討論

（帶虛線的位置代表不需要判斷）

可以看到，2->1->3的距離為2->1的最短距離加1->3的最短距離，即g[2][1]+g[1][3] = 23，這個(gè)距離并不比g[2][3]小，因此不需要更新

而3->1->2的距離為11，小于原來的值MAX，因此更新，同時(shí)path[3][2]也更新為3->1->2的終點(diǎn)的前繼節(jié)點(diǎn)即1

3.重復(fù)第二步直到所有節(jié)點(diǎn)都已作為中間點(diǎn)

1->2->3的距離為g[1][2]+g[2][3] = 10，比原來的13更小，因此將g[1][3]更新，path[1][3] = 2

3->2->1的距離為g[3][2]+g[2][1] = 21，比g[3][1]大，不更新

1->3->2的距離為21，比g[1][2]大，不更新

2->3->1的距離為g[2][3]+g[3][1] = 9，比原來的10更小，因此將g[2][1]更新，path[2][1] = 3

至此，我們就得到了圖中任意兩點(diǎn)間的最短路徑長度了

而最短路徑本身，則可以根據(jù)矩陣path中的值推出來，例如要求從2到1的最短路徑，首先知道終點(diǎn)為節(jié)點(diǎn)1，根據(jù)path[2][1]知道下一個(gè)節(jié)點(diǎn)3，再根據(jù)path[2][3]知道下一個(gè)節(jié)點(diǎn)2，最后path[2][2]為-1說明路徑走到結(jié)尾，因此完整的最短路徑就為2->3->1

---

三、代碼

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define INF 0x3f3f3f3f
using namespace std;#define N 210
#define M 20010int n, m, k;
int g[N][N]; //存儲從i到j(luò)的最短路徑長度
int path[N][N] = {-1}; //path[i][j]存儲從i到j(luò)最短路徑的終點(diǎn) 的 前繼節(jié)點(diǎn)void Floyd()
{for(int i = 1; i <= n; i++){g[i][i] = 0; //自己到自己的路徑長度設(shè)置為0path[i][i] = -1; //自己到自己的路徑設(shè)置為-1}for(int k = 1; k <= n; k++) //代表從i經(jīng)過k到j(luò)的最短路徑{for (int i = 1; i <= n; i++) //第i行{for (int j = 1; j <= n; j++) //第j列{if(i == j || i == k || j == k) //多余情況continue;if(g[i][k] + g[k][j] < g[i][j]) //從i經(jīng)過k到j(luò)的最短路徑 比 原先從i到j(luò)的最短路徑更短{g[i][j] = g[i][k] + g[k][j]; //更新從i到j(luò)的最短路徑path[i][j] = path[k][j]; //更新從i到j(luò)最短路徑的終點(diǎn) 的 前繼節(jié)點(diǎn)}}}}
}void solve()
{memset(g, 0x3f, sizeof g);cin >> n >> m >> k;for(int i = 0;i < m; i++){int a, b, w;cin >> a >> b >> w;g[a][b] = min(g[a][b], w); //可能存在重邊path[a][b] = a; //初始時(shí)從a到b最短路徑終點(diǎn)的前繼節(jié)點(diǎn)就是a本身}Floyd(); //Floyd算法for (int i = 0; i < k; i++){int a, b;cin >> a >> b;if(g[a][b] > INF / 2)cout << "impossible" << endl;elsecout << g[a][b] << endl;}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;//cin >> t;while(t--)solve();return 0;
}

完.