---
tags: APCS
---

# Floyd-Warshall 演算法

digraph G {
    node[shape=circle]

    N1 [label=1]
    N2 [label=2]
    N3 [label=3]
    N4 [label=4]
    N5 [label=5]

    {rank=source;N2}
    {rank=same;N1,N3}
    {rank=same;N5,N4}

    N2->N4 [label=1]
    N2->N5 [label=7]
    N1->N2 [label=3]
    N1->N3 [label=8]
    N1->N5 [label=-4]
    N3->N2 [label=4]
    N4->N1 [label=2]
    N4->N3 [label=-5]
    N5->N4 [label=6]
}

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

//---------------------------------------------------------------------------
// 測試資料
//
// 第一行，一個整數 n 表示有幾個節點
// 剩下一直到結尾的每一行的 3 個整數都代表一條邊，格式為 v1 v2 w
//  v1 v2 代表線的兩個端點，
//  w 代表這條線的權重(或成本)
//
string input = "\
5\n\
1 2 3\n\
1 3 8\n\
1 5 -4\n\
2 4 1\n\
2 5 7\n\
3 2 4\n\
4 1 2\n\
4 3 -5\n\
5 4 6\n";
//---------------------------------------------------------------------------

typedef vector<vector<int>> Graph;

int main()
{
    stringstream sin(input);
    int n, a, b, w;

    sin >> n;
    Graph   g(n+1, vector<int>(n+1, INT32_MAX));    // nxn 的 2 維陣列，每一格都先填 INT32_MAX
    
    for (int i = 1; i <= n; i++)
        g[i][i] = 0;

    while (sin >> a >> b >> w) {
        g[a][b] = w;
    }

    // Floyd-Warshall 演算法
    //
    // Gij = min(Gij, Dik + Dkj)
    //
    for (int k = 1; k <= n; k++) {
        bool modified = false;
        for (int i = 1; i <=n; i++) {
            if (i == k) continue;
            for (int j = 1; j <= n; j++) {
                if (j == k) continue;
                if (g[i][k] == INT32_MAX || g[k][j] == INT32_MAX) continue; // 跳過目前沒有值的點
                if (g[i][k] + g[k][j] < g[i][j]) {
                    g[i][j] = g[i][k] + g[k][j];
                    modified = true;
                }
            }
        }
        if (!modified)  // 如果此回合沒有更新，可以提早離開
            break;
    }
    cout << "Distance: \n";
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << g[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}