---
tags: APCS
---

# Bellman-Ford 演算法

digraph G {
    rankdir=LR
    splines="line"
    node[shape=circle]
    {rank=same;1,2}
    {rank=same;3,4}
    0 -> 1 [label=5]
    0 -> 2 [label=-2]
    1 -> 3 [label=1]
    2 -> 1 [label=2]
    2 -> 4 [label=3]
    3 -> 2 [label=2]
    3 -> 4 [label=7]
    3 -> 5 [label=3]
    4 -> 5 [label=10]
}

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>

using namespace std;

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

// Bellman-Ford 需要窮舉每一條邊來進行鬆弛，所以要包含兩端點
struct Edge {
    int from, to, weight;
};

// 用結構紀錄圖的組態
struct Graph {
    int n;                  // 總節點數
    vector<Edge>    edge;   // 所有邊的列表
};

vector<int> sssp_bellman_ford(Graph &g, int src)
{
    vector<int>     dist(g.n, INT32_MAX);
    dist[src] = 0;

    for (int i = 0; i < g.n; i++) { // 跑 n 個回合
        int modified = false;
        for (auto &e: g.edge) {     // 窮舉每條邊進行鬆弛
            auto &cur_dist = dist[e.from];
            if (cur_dist != INT32_MAX) {    // 有值的再處理就可以了，無限大的先跳過
                if (cur_dist + e.weight < dist[e.to]) {     // 可以鬆弛的話
                    dist[e.to] = cur_dist + e.weight;       // 更新 to 的最短距離
                    modified = true;                        // 本回合有更新
                }
            }
        }
        if (!modified)      // 如果此回合沒有變更，就可以提早離開
            break;
    }
    return dist;
}

int main()
{
    stringstream    sin(input);
    Graph   G;
    int     a, b, r;

    sin >> G.n;
    while (sin >> a >> b >> r) {
        G.edge.push_back({a, b, r});
    }
    // 印出從每一點當起點時，至各點的最短距離
    for (int i = 0; i < G.n; i++) {
        auto dist = sssp_bellman_ford(G, i);
        cout << i << ": ";
        copy(dist.begin(), dist.end(), ostream_iterator<int>(cout, " "));
        cout << '\n';
    }
    return 0;
}