---
tags: 成大高階競技程式設計 2021
---

# 2021 Week11 - Graph (MST, SP)

註：:bulb: 代表相對少見、較進階或與主題關聯性較低的內容，讀者可自行斟酌觀看。

---

# 最小生成樹（MST, minimum spanning tree）

graph {
    rankdir=LR;
    node [shape=circle, label=""];
    C; B;
    edge [style=dashed, color=gray];
    A -- B [label="8"];
    C -- E [label="9"];
    D -- F [label="3"];
    E -- F [label="7"];
    edge [style=bold, color=black];
    A -- C [label="4"];
    B -- D [label="2"];
    C -- D [label="7"];
    D -- E [label="6"];
    B -- F [label="1"];
}

生成樹，是包含所有點的子圖，並且它是一棵樹；
最小生成樹，是所有生成樹中，邊權重總和最小的。

## Kruskal's algorithm

graph {
    rankdir=LR;
    node [shape=circle, label=""];
    C; B;
    edge [style=dashed, color=gray];
    D -- F [label="3"];
    edge [style=dashed, color=black];
    A -- B [label="8"];
    C -- E [label="9"];
    E -- F [label="7"];
    C -- D [label="7"];
    D -- E [label="6"];
    edge [style="bold, dashed", color=black];
    A -- C [label="4"];
    edge [style=bold];
    B -- D [label="2"];
    B -- F [label="1"];
}

Kruskal's algorithm 每次在不會形成圈的邊中，選一條最小的，直到形成一棵樹為止。

> Kruskal's algorithm 是一個 greedy algorithm。

> #### 證明
> 令 Kruskal's algorithm 找到的樹為 $T$，而對於其他的生成樹 $U$，
> 若 $U$ 的邊 $e$ 不在 $T$ 中，則將 $e$ 加入 $T$ 的話，會形成一個圈，
> 圈上一定至少有另一條邊 $f$ 不屬於 $U$，
> 而因為 Kruskal's algorithm 將 $f$ 加入 $T$ 而非 $e$，代表 $w_{e}\ge w_{f}$。
>
> 我們將 $e$ 換成 $f$，得到另外一棵生成樹 $V=U-e+f$，$W_U\ge W_V$，
> 經過多次轉換，$U$ 一定會變為 $T$，$W_U\ge W_V\ge\cdots\ge W_T$，
> 所以對於任意生成樹 $U$，$W_U\ge W_T$，得證 $T$ 是最小生成樹。

實作上，要判斷會不會形成圈，也就是判斷連通分量，可以用並查集來記錄。

vector<tuple<int, int, long long>> Kruskal(int n, vector<tuple<long long, int, int>>& edges) {
    vector<tuple<int, int, long long>> mst{};
    DSU dsu{n};

    sort(edges.begin(), edges.end());
    for (auto& [w, u, v] : edges)
        if (dsu.find(u) != dsu.find(v))
            dsu.unionn(u, v), mst.emplace_back(u, v, w);
    return mst;
}

時間複雜度 $O(|E|\log|E|+|E|\cdot\alpha)=O(|E|\log|E|)$。

<hr class="dashed">

## Prim's algorithm

graph {
    rankdir=LR;
    node [shape=circle, label=""];
    C; B;
    edge [style=dashed, color=gray];
    D -- F [label="3"];
    A -- C [label="4"];
    C -- E [label="9"];
    edge [color=black];
    E -- F [label="7"];
    D -- E [label="6"];
    A -- B [label="8"];
    edge [style="bold, dashed", color=black];
    C -- D [label="7"];
    edge [style=bold];
    B -- D [label="2"];
    B -- F [label="1"];
}

跟 Kruskal's algorithm 過程中會形成森林不同，Prim's algorithm 維護一棵樹 $T$，
每次加入符合 $u\in T, v\notin T$ 的邊 $(u,v)$ 中最小邊，同時也是加入一個點 $v$，
當加入所有點後，T 就是最小生成樹。

> Prim's algorithm 也是一個 greedy algorithm。

> #### 證明
> 令 Prim's algorithm 找到的樹為 $T$，而對於其他的生成樹 $U$，
> 依照 Prim's algorithm 加入邊的順序，令 $T$ 中第一個不在 $U$ 的邊為 $e$，
> 而在這之前被加入的點集合為 $S$，
> 因為 $U$ 是樹，$U$ 中還是有一條路徑連接 $e$ 的二個端點，
> 而這條路徑上有一條邊 $f$，端點分別屬於 $S$ 以及不屬於 $S$，
> 而在 Prim's algorithm 選擇加入 $e$ 時，沒有選擇 $f$，代表 $w_{f}\ge w_{e}$。
>
> 我們將 $f$ 換成 $e$，得到另外一棵生成樹 $V=U-f+e$，$W_U\ge W_V$，
> 經過多次轉換，$U$ 一定會變為 $T$，$W_U\ge W_V\ge\cdots\ge W_T$，
> 所以對於任意生成樹 $U$，$W_U\ge W_T$，得證 $T$ 是最小生成樹。

vector<tuple<int, int, long long>> Prim(const vector<vector<pair<int, long long>>>& adj) {
    const auto& n{adj.size()};
    vector<tuple<int, int, long long>> mst{};

    vector<bool> found(n, false);
    using ti = tuple<long long, int, int>;
    priority_queue<ti, vector<ti>, greater<ti>> pq{};
    found[0] = true;
    for (auto& [v, w] : adj[0]) pq.emplace(w, 0, v);

    for (int i{0}; i < n - 1; ++i) {
        int mn, u, v;
        do {
            tie(mn, u, v) = pq.top(), pq.pop();
        } while (found[v]);
        found[v] = true, mst.emplace_back(u, v, mn);
        for (auto& [x, w] : adj[v]) pq.emplace(w, v, x);
    }
    return mst;
}

時間複雜度為 $O(|V|+|E|\log|E|)=O(|E|\log|E|)$。

> :bulb:上述做法以邊進行排序，如果改成以點的觀點排序，
> 自行實作二元堆積，並透過 [decrease-key](https://en.wikipedia.org/wiki/Binary_heap#Decrease_or_increase_key) 的方式更新，
> 時間複雜度可降低為 $O((|V|+|E|)\log|V|)=O(|E|\log{|V|})$。

---

# 最短路徑（SP, shortest path）

digraph {
	rankdir=LR;
	node [label=""];
	edge [style=dashed];
	A [label="u"];
	F [label="v"];
	A -> B [label="3", style=bold];
	A -> D [label="8"];
	B -> C [label="2", style=bold];
	C -> F [label="5"];
	D -> C [dir="back", label="1", style=bold];
	D -> E [label="2", style=bold];
	E -> F [label="1", style=bold];
}

$u$ 到 $v$ 的最短路徑是指，以 $u$ 為起點，$v$ 為終點的路徑中，邊的權重總和最小的一條路徑。

## 單源最短路徑問題（SSSP, single-source shortest path problem）

單源最短路徑問題，是要找出一個起點 $u$，到其他所有點的最短路徑。

## Bellman-Ford algorithm

之前在 [DP](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-DP#%E5%96%AE%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%91%EF%BC%88Single-source-shortest-path%EF%BC%89) 時講過的方法，沒辦法處理有環的圖，這邊我們定義一個不一樣的問題，
定義 $sp(S,V,i)$ 代表從 $S$ 到 $V$，長度不超過 $i$ 的最短路徑；
如果 $sp(S,V,i)$ 長度小於 $i$，則它就是 $sp(S,V,i-1)$；
否則會是其他點長度不超過 $i-1$ 的最短路徑 $sp(S,U,i-1)$，再加上一條邊 $(U,V)$。

:::success
$sp(S,V,i)=\min(sp(S,V,i-1), \min\limits_{(U,V)\in E}(sp(S,U,i-1)+w(U,V)))$
:::

> 沒有負環的話，最短路徑最多包含 $n-1$ 條邊，所以 $sp(S,V,n-1)$ 就是最終的答案了。

vector<long long> Bellman_Ford(const vector<vector<pair<int, long long>>>& adj, int s) {
    const auto& n{adj.size()};
    vector<vector<long long>> sp(n, vector<long long>(n, 100000000));
    sp[s][0] = 0;

    for (int i{1}; i < n; ++i) {
        for (int v{0}; v < n; ++v) {
            sp[v][i] = sp[v][i - 1];
            for (auto& [u, w] : adj[v])
                sp[v][i] = min(sp[v][i], sp[u][i - 1] + w);
        }
    }

    vector<long long> d(n);
    for (int v{0}; v < n; ++v) d[v] = sp[v][n - 1];
    return d;
}

時間複雜度為 $O(|V||E|)$

<hr class="thin">

這樣空間複雜度有點高，我們可以使用之前說過的 rolling dp 的技巧，只留下二行的結果。

> 再偷懶一點，我們只用一行。

vector<long long> Bellman_Ford(const vector<vector<pair<int, long long>>>& adj, int s) {
    const auto& n{adj.size()};
    vector<long long> sp(n, 100000000);
    sp[s] = 0;

    for (int i{1}; i < n; ++i) {
        for (int v{0}; v < n; ++v) {
            for (auto& [u, w] : adj[v])
                sp[v] = min(sp[v], sp[u] + w);
        }
    }

    return sp;
}

應該有人發現，這樣我們根本沒有乖乖地用到 $SP(S,U,i-1)$ 的答案，
有些變成了用 $SP(S,U,i-1)$ 去更新；
但演算法的核心價值在於「考慮了所有長度小於 $i$ 的路徑」，
而非「只考慮長度小於 $i$ 的路徑」，所以最終一樣可以得到正確答案。

> 利用鄰點更新最短路徑，這個動作被稱為 [Relaxation](https://en.wikipedia.org/wiki/Relaxation_(approximation))。

<hr class="dotted">

### Shortest Path Faster Algorithm

上面的做法，可以發現到，很多點的最短路徑根本沒有被更新，
那再一次去嘗試更新鄰點的最短路徑根本是沒有意義的；
所以演算法就可以改成，最短路徑有被更新的點，再去嘗試更新其他點就好。

> 這邊讓它跑 $n$ 輪，第 $n$ 輪時不應該有點再被更新了，否則的話就代表它有負環。

template <typename T>
optional<vector<optional<T>>> Bellman_Ford(const vector<vector<pair<int, T>>>& adj, int s) {
    const auto& n{adj.size()};
    vector<optional<T>> d(n, nullopt);
    d[s] = 0;

    queue<int> qu{}, qu2{};
    vector<bool> in(n, false), in2(n, false);
    qu.push(s), in[s] = true;
    for (int i{0}; i < n; ++i) { // at most n-1 edges
        while (!qu.empty()) {
            int u{qu.front()};
            qu.pop(), in[u] = false;
            for  (auto& [v, w] : adj[u])
                if (!d[v] || d[v] > d[u].value() + w) { // relax
                    d[v] = d[u].value() + w;
                    if (!in2[v]) qu2.push(v), in2[v] = true;
                }
        }
        qu.swap(qu2), in.swap(in2);
    }

    if (qu.empty()) return d;
    return nullopt; // if negative cycle
}

時間複雜度最差的情況不變，但在隨機的圖下，平均複雜度為 $O(E)$。[^SPFA]

<hr class="dashed">

## Dijkstra's algorithm

一定有些點的最短路徑長度為 $1$，在 Bellman-Ford 演算法中，
這樣的點還是會被更新（與持續嘗試更新其他點），就浪費了很多計算量。

今天假設邊都是非負權重，有一個點集合 $S$，
則 $S$ 中最短路徑最短的點，最短路徑只包含 $V-S$ 中的點，
所以我們就可以持續地找出最短路徑最短的點 $u$，
接著集合就只剩下 $S-u$（子問題），這就是一個 greedy algorithm。

> 因為「$S$ 中最短路徑最短的點，最短路徑只包含 $V-S$ 中的點」，
> 等價於我們只需要計算所有點只經過 $V-S$ 的最短路徑，然後找最短的，
> 因為如果某個點的最短路徑還要經過 $S$ 中的點，代表它一定不是那個 $u$。
>
> 而我們只要每次找到 $u$ 後，去更新其他點的最短路徑，
> 就能快速地維護所有點只經過 $V-S$ 的最短路徑。

template <typename T>
vector<optional<T>> Dijkstra(const vector<vector<pair<int, T>>>& adj, int s) {
    const auto& n{adj.size()};
    vector<optional<T>> d(n, nullopt);
    d[s] = 0;

    vector<bool> found(n, false);
    using pq_t = pair<T, int>;
    priority_queue<pq_t, vector<pq_t>, greater<pq_t>> pq{};
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [_, u]{pq.top()}; pq.pop();
        if (found[u]) continue;
        found[u] = true;
        for (auto& [v, w] : adj[u])
            if (!d[v] || d[v] > d[u].value() + w) {
                d[v] = d[u].value() + w;
                pq.emplace(d[v].value(), v);
            }
    }

    return d;
}

複雜度為 $O(|E|\log|E|+|E|\log|E|)=O(|E|\log|E|)=O(|E|\log|V|)$。

> 一個點可能會被前面最短路徑較短的點更新，最多會到 $O(|V|)$ 次，
> 但全部的點被更新（被丟進 pq）的次數還是不會超過 $O(|E|)$，
> 不然也可以透過 [Decrease key](https://en.wikipedia.org/wiki/Binary_heap#Decrease_or_increase_key) 的方式將 pq 的大小限制在 $O(|V|)$，但差別不大，
> 因為$|E|=O(|V|^2)$，因為取對數後，漸進符號（asymptotic notation）是一樣的。

<hr class="dashed">

## 所有點對最短路徑問題（APSP, all-pairs shortest path problem）

所有點對最短路徑問題，是要找尋任意二點之間的最短路徑。

## Floyd–Warshall algorithm

定義 $sp(i,j,k)$ 為 $i$ 到 $j$，且中間點只能為 ${0\dots k}$ 的最短路徑，
則 $sp(i,j,k)$ 若有經過 $k$，就是 $sp(i,k,k-1)$，再加上 $sp(k,j,k-1)$。

:::success
$sp(i,j,k)=\min(sp(i,j,k-1), sp(i,k,k-1)+sp(k,j,k-1))$
:::

> 一樣透過 rolling dp 的技巧，所以只需要二維的空間。

template <typename T>
vector<vector<optional<T>>> Floyd_Warshall(const vector<vector<optional<T>>>& adj) {
    const auto& n{adj.size()};
    auto d{adj};

    for (int i{0}; i < n; ++i) d[i][i] = 0;
    for (int k{0}; k < n; ++k)
        for (int i{0}; i < n; ++i)
            for (int j{0}; j < n; ++j) {
                if (!d[i][k] || !d[k][j]) continue; // no value
                if (!d[i][j] || d[i][j] > d[i][k].value() + d[k][j].value())
                    d[i][j] = d[i][k].value() + d[k][j].value();
            }

    return d;
}

複雜度為 $O(|V|^3)$。

---

# References

* Wikipedia - [Kruskal's algorithm](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm)
* Wikipedia - [Prim's algorithm](https://en.wikipedia.org/wiki/Prim's_algorithm)

[^SPFA]: Wikipedia - [Shortest Path Faster Algorithm - Running time](https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm#Running_time)

<style>

hr.thin {
height: 0.5px;
}

hr.dotted {
border-top: dotted;
height: .0em;
color: #777777;
background-color: #ffffff;
}

hr.dashed {
border-top: dashed;
height: .0em;
color: #777777;
background-color: #ffffff;
}

/* Gradient transparent - color - transparent */
hr.gradient {
border: 0;
height: 1px;
background-image: linear-gradient(to right, rgba(0, 0, 0, 0), rgba(0, 0, 0, 0.75), rgba(0, 0, 0, 0));
}

/* Flaired edges, by Tomas Theunissen */
hr.flaired {
overflow: visible;
height: 30px;
border-style: solid;
border-color: black;
border-width: 1px 0 0 0;
border-radius: 20px;
background-color: #ffffff;
}
hr.flaired:before { /* Not really supposed to work, but does */
display: block;
content: "";
height: 30px;
margin-top: -31px;
border-style: solid;
border-color: black;
border-width: 0 0 1px 0;
border-radius: 20px;
}

</style>