---
tags: APCS
---

# Dijkstra 演算法

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

#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 4\n\
0 2 2\n\
1 2 1\n\
1 3 5\n\
2 3 8\n\
2 4 10\n\
3 4 2\n\
3 5 6\n\
4 5 3\n";
//---------------------------------------------------------------------------

struct Edge {
    int to, weight;
};

typedef vector<Edge>    Node;
typedef vector<Node>    Graph;

vector<int> sssp_djkstra(Graph &g, int src)
{
    vector<int>     dist(g.size(), INT32_MAX);
    vector<bool>    selected(g.size());
    int remain_nodes = g.size();
    dist[src] = 0;
    while (remain_nodes > 0) {
        int min_dist = INT32_MAX;
        int me = 0;
        // 找未展開的點中距離最小的
        for (int i = 0; i < g.size(); i++) {
            if (!selected[i] && dist[i] < min_dist) {
                min_dist = dist[i];
                me = i;
            }
        }
        int cur_dist = dist[me];
        selected[me] = true;        // 標記這點已被處理過

        for (auto &e: g[me]) {
            // 鬆弛尚未處理過的相鄰點
            if (!selected[e.to] && cur_dist + e.weight < dist[e.to]) {
                dist[e.to] = cur_dist + e.weight;
            }
        }
        remain_nodes--;
    }
    return dist;
}

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

    sin >> n;
    G.resize(n);    // 有 n 個節點，從 0 號開始編號

    while (sin >> a >> b >> r) {
        G[a].push_back({b, r});
        G[b].push_back({a, r});
    }

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

    return 0;
}