一、簡述

\(Floyd\) 算法是一種可以快速求解圖上所有頂點之間最短路徑的算法。

\(Bellman-Ford\) 和 \(Dijkstra\) 算法求解的都是從一個起始點開始的最短路。如果想要求解圖中所有頂點之間的最短路，就需要枚舉每個點做為起點，這樣十分低效。\(Floyd\) 算法(也稱 \(Floyd-Warshall\) 算法)處理用鄰接矩陣存儲的有向圖(無向圖的一條邊可以看做有向圖的兩條邊)十分方便。

二、Floyd算法

memset(f, 127, sizeof f);
f[0][i][j] = a[i][j];

for (int k = 1; k <= n; k++)
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			f[k][i][j] = min(f[k - 1][i][j], f[k - 1][i][k] + f[k - 1][k][j]);

• \(f[k][i][j]\) 表示從 \(i\) 到 \(j\) 并且可以經(jīng)過 \(1\) 至 \(k\) 的最短路徑，\(f[0][i][j]\) 表示從 \(i\) 到 \(j\) 并且不經(jīng)過任何中間點的最短路徑。
• \(a[i][j]\) 表示從 \(i\) 到 \(j\) 的邊的長度，\(a[i][i]=0\)。

\(Floyd\) 算法是動態(tài)規(guī)劃的思想。在轉(zhuǎn)移方程中，從 \(i\) 到 \(j\) 的最短路徑可以經(jīng)過頂點 \(k\)，也可以不經(jīng)過頂點 \(k\)，經(jīng)過頂點 \(k\)，則 \(k\) 將路徑分為兩段，前后兩段最多只能經(jīng)過 \(1\) 至 \(k-1\)，不經(jīng)過頂點 \(k\)，則最多經(jīng)過 \(1\) 至 \(k-1\)。

那么上述代碼可以空間優(yōu)化嗎？答案是肯定的，優(yōu)化后的代碼如下

memset(f, 127, sizeof f);
f[i][j] = a[i][j];

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] < 1 << 30 && f[k][j] < 1 << 30) // 注意int類型數(shù)據(jù)范圍
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

優(yōu)化后，驗證一下正確性，在加入頂點 \(k\) 之前，\(f[i][j]\) 就相當(dāng)于 \(f[k-1][i][j]\)，但是 \(f[i][k]\) 以及 \(f[k][j]\) 是有可能在 \(f[i][j]\) 之前被覆蓋的，但是注意 \(f[k][i][j]\) 的含義為從 \(i\) 到 \(j\) 并且可以經(jīng)過 \(1\) 至 \(k\) 的最短路徑，那么 \(1\) 至 \(k\) 為中間點，則 \(f[k-1][i][k]=f[k][i][k]\) 并且 \(f[k-1][k][j]=f[k][k][j]\)，因此可以使用 \(f[i][k] + f[k][j]\) 來替換。

關(guān)于路徑的記錄，可以使用 \(path\) 數(shù)組在距離更新時來記錄，\(path[i][j]=k\)，表示從 \(i\) 到 \(j\) 經(jīng)過中間點 \(k\)(\(path[i][j]=-1\) 表示 \(i\) 和 \(j\) 直接相連)，然后利用 \(k\) 將路徑分為兩部分，依次遞歸輸出。

模板題AcWing854.Floyd求最短路

題目描述

給定一個 \(n\) 個點 \(m\) 條邊的有向圖，圖中可能存在重邊和自環(huán)，邊權(quán)可能為負(fù)數(shù)。
再給定 \(k\) 個詢問，每個詢問包含兩個整數(shù) \(x\) 和 \(y\)，表示查詢從點 \(x\) 到點 \(y\) 的最短距離，如果路徑不存在，則輸出 impossible。
數(shù)據(jù)保證圖中不存在負(fù)權(quán)回路。

輸入格式

第一行包含三個整數(shù) \(n,m,k\)。
接下來 \(m\) 行，每行包含三個整數(shù) \(x,y,z\)，表示存在一條從點 \(x\) 到點 \(y\) 的有向邊，邊長為 \(z\)。
接下來 \(k\) 行，每行包含兩個整數(shù) \(x,y\)，表示詢問點 \(x\) 到點 \(y\) 的最短距離。

輸出格式

共 \(k\) 行，每行輸出一個整數(shù)，表示詢問的結(jié)果，若詢問兩點間不存在路徑，則輸出 impossible。

數(shù)據(jù)范圍

\(1≤n≤200\)，
\(1≤k≤n^2\)，
\(1≤m≤20000\)，
圖中涉及邊長絕對值均不超過 \(10000\)。

輸入樣例

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

輸出樣例

impossible
1

C++代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 1e9;

int n, m, q;
int dist[N][N];

void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == j) 
                dist[i][j] = 0;
            else 
                dist[i][j] = INF;
        }
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        dist[x][y] = min(dist[x][y], z);
    }
    floyd();
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (dist[x][y] > INF / 2) 
            puts("impossible");
        else 
            cout << dist[x][y] << endl;
    }
    return 0;
}

三、Floyd算法的應(yīng)用

這里給出一個和 \(Floyd\) 算法思想相關(guān)的題目。

Daimayuan Online Judge.刪點游戲

題目描述

給你一張 \(n\) 個頂點的有向簡單圖，頂點編號從 \(1\) 到 \(n\)，我們要把所有頂點一個一個刪完。小蝸每次會刪掉圖中的一個頂點和所有與它相連的邊，小蝸想知道每刪去一個頂點之后圖中所有點對的距離之和。

輸入格式

第一行一個整數(shù) \(n\)，表示頂點數(shù)。
接下來 \(n\) 行，每行 \(n\) 個整數(shù)，組成一個 \(n×n\) 的矩陣 \(A\) 表示這張圖的鄰接矩陣，矩陣第 \(i\) 行第 \(j\) 列表示 \(i\) 號頂點到 \(j\) 號頂點有一條邊權(quán)為 \(A[i][j]\) 的邊。
接下來一行，輸入 \(n\) 個數(shù) \(x_1,x_2,...,x_n\)，代表刪除頂點的順序。

輸出格式

輸出一行 \(n\) 個數(shù)依次表示刪除了第 \(0\) 個點（一個點都沒刪除）到第 \(n?1\) 個點（圖中還剩下一個點）后，圖中所有剩下的點對的距離之和。

數(shù)據(jù)范圍

對于所有數(shù)據(jù)，保證 \(2≤n≤300,1≤A[i][j]≤10000,A[i][i]=0,1≤x_i≤n\)。

輸入樣例

2
0 5
4 0
1 2

輸出樣例

9 0

解題思路

根據(jù)題目描述，按照給定的順序刪除頂點，計算剩余各點之間的最短路的距離和。在 \(Floyd\) 算法中，在求解過程中是依次枚舉中間點 \(k\)，那么就相當(dāng)于每次都增加一個頂點，因此此問題可以逆向為按照給點的順序依次增加頂點，計算圖中已有頂點之間的最短路的距離和。
在頂點的增加中，利用布爾數(shù)組來表示某一頂點是否在圖中，在計算最短路距離和的時候需要考慮當(dāng)前的頂點是否在圖中。文章來源地址http://www.zghlxwxcb.cn/news/detail-711547.html

C++代碼

#include <bits/stdc++.h> 
using namespace std;
const int N = 310, M = 65;
typedef long long LL;

int n;
int x[N], dist[N][N];
bool b[N];
int a[N];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &dist[i][j]);
	for (int i = 1; i <= n; i++)
		scanf("%d", &x[i]);
	for (int l = n; l; l--) {
		int k = x[l];
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		b[k] = true;
		int ans = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (b[i] && b[j])
					ans += dist[i][j];
		a[l] = ans;
	}
	for (int i = 1; i <= n; i++)
		printf("%d ", a[i]);
    return 0;
}

到了這里，關(guān)于搜索與圖論2.2-Floyd算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！