【圖論——第六講】Floyd算法求多源最短路問題

文章目錄

• ​​一、前言​​
• ​​二、Floyd算法​​
• ​​最後​​

一、前言

單源最短路，指的是求一個點，到其他所有點的最短距離。​

​即起點是固定的，單一的​

​​ 那麼多源最短路就是指​

​每一個點到圖中其他頂點的最短路​

​

注意：最短路問題的核心在于，把問題抽象成一個最短路問題，并建圖。圖論相關的問題，不側重于算法原理，而側重于對問題的抽象。

二、Floyd算法

Floyd 屬于多源最短路徑算法，能夠求出任意2個頂點之間的最短路徑，支援負權邊

時間複雜度 O(n^3), n 表示點數。

Floyd算法時間複雜度很高，但效率比執行 n次 Dijkstra 算法要好。

算法解釋

從任意頂點 i 到任意頂點 j 的最短路徑不外乎兩種可能

① 直接從 i 到 j

② 從 i 經過若幹個頂點到 j

• 假設 dist(i，j) 為頂點 i 到頂點 j 的最短路徑的距離
• 對于每一個頂點 k，檢查 dist(i，k) + dist(k，j)＜dist(i，j) 是否成立
• 如果成立，證明從 i 到 k 再到 j 的路徑比 i 直接到 j 的路徑短，設定 dist(i，j) = dist(i，k) + dist(k，j)
• 當我們周遊完所有結點 k，dist(i，j) 中記錄的便是 i 到 j 的最短路徑的距離

算法實作

初始化

for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
// 算法結束後，d[a][b]表示a到b的最短距離      

核心代碼隻有四行

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

求任意兩個點之間的最短路

給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環，邊權可能為負數。

再給定k個詢問，每個詢問包含兩個整數x和y，表示查詢從點x到點y的最短距離，如果路徑不存在，則輸出“impossible”。

資料保證圖中不存在負權回路（負權環）因為帶有負權回路的圖沒有最短路徑

第一行包含三個整數n，m，k

接下來m行，每行包含三個整數x，y，z，表示點x和點y之間存在一條有向邊，邊長為z。

接下來k行，每行包含兩個整數x，y，表示詢問點x到點y的最短距離。

共k行，每行輸出一個整數，表示詢問的結果，若詢問兩點間不存在路徑，則輸出“impossible”。

樣例

3 3 2

1 2 1

2 3 2

1 3 1

2 1

1 3

impossible

1

#include <iostream>
using namespace std;

const int N = 210, M = 2e+10, INF = 1e9;

int n, m, k, x, y, z;
int d[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++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    //            if(d[i][j]>d[i][k]+d[k][j])
     //           d[i][j]=d[i][k]+d[k][j];
}

int main() {
    cin >> n >> m >> k;
    //初始化
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
    while(m--) {
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);
        //注意儲存最小的邊
    }
    floyd();
    while(k--) {
        cin >> x >> y;
        if(d[x][y] > INF/2) puts("impossible");
        //由于有負權邊存在是以約大過INF/2也很合理
        else cout << d[x][y] << endl;
    }
    return 0;
}      

最後

莫言真理無窮盡，寸進自有寸進歡