DSA Graph (2) - HackMD

# 【資工考研】DSA: Graph (2) Shortest Path Problem [前一篇：【資工考研】DSA: Graph (1)](https://hackmd.io/@RyoukiWei/graph_1) 1. Graph Representations 2. BFS & DFS 3. Shortest Path Problem 4. Minimum Spanning Tree 5. Articulation Point 6. Flow Network ## Shortest Path Problem <table> <tr> <th></th> <th colspan="3">Single-source Shortest Path</th> <th colspan="2">All-pairs Shortest Path</th> </tr> <tr align="center"> <td>演算法</td> <td>DAG</td> <td>Dijkstra</td> <td>Bellman-Fold</td> <td>Floyd-Warshall</td> <td>Johnson</td> </tr> <tr align="center"> <td>策略</td> <td>利用 tolopological sort</td> <td>greedy</td> <td>DP</td> <td>DP</td> <td>Dijkstra + Bellman-Fold</td> </tr> <tr align="center"> <td>可否有 cycle</td> <td>X</td> <td>O</td> <td>O</td> <td>O</td> <td>O</td> </tr> <tr align="center"> <td>可否有negative cost edge</td> <td>O</td> <td>X</td> <td>O</td> <td>O</td> <td>O</td> </tr> <tr align="center"> <td>可否有negative cycle length</td> <td>X</td> <td>X</td> <td>X</td> <td>X</td> <td>X</td> </tr> </table> ## Single-source Shortest Path Problem 給定 $G = (V, E)$ 為一 directed weighted graph，其 weight function 為 $w: E\rightarrow \mathbb{R}$ 令 $w(P)$ 為 path $P$ 上所有邊之權重和，稱之為 $P$ 之權重 - $\forall u,v\in V$ 定義 $\delta (u,v)$ 為所有自 $u$ 到 $v$ 的路徑中權重最小者，若 $u$ 無法抵達 $v$ 則 $\delta (u,v) = \infty$ - 若 $P$ 為一條自 $u$ 到 $v$ 的 path 滿足 $w(P) = \delta (u,v)$，則稱 $P$ 為自 $u$ 到 $v$ 的最短路徑 (shortest path) > [!Tip] > 給定起點 $s$ (source vertex)，如何求 $s$ 到各點之最短路徑，此即 single-source shortest path problem > [!Note] > 給定 $T$ 為 root 是 $s$ 的 tree 且 $T$ 是 $G$ 之子圖，若 $\forall v \in V$ ， $T$ 中 $s$ 到 $v$ 的路徑皆為 $G$ 上 $s$ 到 $v$ 的最短路徑，則稱 $T$ 為 shortest path tree > > $\forall v\in V$ 在 shortest path tree 中 $v$ 之 parent (predecessor of $v$) 記作 $v.\pi$ > $\forall v\in V$ ，$v.\mathrm{d}$ 表示 $s$ 到 $v$ 之 shortest path esimate，在最短路徑演算法中，此值會被不斷更新，直到演算法執行結束時方為 $s$ 到 $v$ 之最短路徑長定義幾個副程式先調整一下 `Graph`： ```cpp! // Don't mind struct pair_hash { template <class T1, class T2> std::size_t operator() (const std::pair<T1, T2>& pair) const noexcept { auto hash1 = std::hash<T1>{}(pair.first); auto hash2 = std::hash<T2>{}(pair.second); return hash1 ^ (hash2 << 1); } }; struct Graph { int num; std::vector<std::vector<int>> adjList; std::unordered_map<std::pair<int, int>, int, pair_hash> edgeWeights; struct Vertex { int d; // Shortest path estimate Vertex* pi; // Predecessor in shortest path }; std::vector<Vertex> vertices; Graph(int n) : num(n), adjList(n), vertices(n) {} void addEdge(int u, int v, int weight) { adjList[u].push_back(v); edgeWeights[{u, v}] = weight; } int w(int u, int v) const noexcept { auto it = edgeWeights.find({u, v}); if (it != edgeWeights.end()) return it->second; return INT_MAX; // If edge doesn't exist, treat as ∞ } }; ``` ```cpp! void initializeSingleSource(Graph &g, int s) { for (auto &v : g.vertices) { v.d = INT_MAX; // ∞ v.pi = nullptr; } g.vertices[s].d = 0; } void relax(Graph &g, int u, int v) { const int weight = g.w(u, v); if (g.vertices[v].d > g.vertices[u].d + weight) { g.vertices[v].d = g.vertices[u].d + weight; g.vertices[v].pi = &g.vertices[u]; } } ``` ### DAG Algorithm 在 DAG 上可以在 linear time 找出 shortest path 關鍵在於使用 [topological sort](https://hackmd.io/@RyoukiWei/graph_1#%E6%89%BE%E5%87%BA-topological-sort) ```cpp! void DAGShortestPath(Graph &g, int s) { auto l = topologicalSort(g); initializeSingleSource(g, s); for (int u : l) { for (int v : g.adjList[u]) { relax(g, u, v); } } } ``` Time complexity: $O(\left| V \right| + \left| E \right|)$ 另外，在 DAG 上求最長路徑 (又稱 critical path) 有至少兩種 linear time 的作法： 1. 把上面最短路徑演算法中， `relax` 裡面所有 $\infty$ 改成 $-\infty$ 並把 $\gt$ 改成 $\lt$ 2. 把 DAG 中所有邊權重乘 $-1$，因為沒有 cycle 的關係，不用擔心會出現 negative cycle ### Dijkstra's Algorithm ```cpp! void dijkstra(Graph &g, int s) { initializeSingleSource(g, s); auto compare = [](const Graph::Vertex *lhs, const Graph::Vertex *rhs) { // for min priority queue based on shortest path estimate return lhs->d > rhs->d; }; std::priority_queue<Graph::Vertex *, std::vector<Graph::Vertex *>, decltype(compare)> minQ(compare); // Add all vertices to the priority queue for (auto &vertex : g.vertices) { minQ.push(&vertex); } while (!minQ.empty()) { // Extract-Min() Graph::Vertex *u = minQ.top(); minQ.pop(); const int uIdx = u - &g.vertices[0]; for (int vIdx : g.adjList[uIdx]) { Graph::Vertex *v = &g.vertices[vIdx]; const int prev = v->d; relax(g, uIdx, vIdx); if (v->d < prev) minQ.push(v); } } } ``` Dijkstra's algorithm 的精神就是 greedy 課本上原本的作法是會準備一個空集合 $S$ 用來蒐集已經計算出最短距離的頂點每次 $\mathrm{Extract-Min()}$ 完，將 $u$ 加入其中 ($S = S\cup \left\{ u \right\}$) 不過這不影響到演算法本身的表達 Dijkstra 最重要的靈魂就在於那個 priority queue 我們使用該資料結構來每回合選出 shortest path estimate 最小的頂點 $u$ 本演算法的時間複雜度會受選擇怎樣的資料結構來作為 priority queue 影響：演算法中的 `while` 執行次數為 $O(\left| V \right|)$，故 1. 如果我們是利用一個大小為 $\left| V \right|$ 的陣列，則每次 $\mathrm{Extract-Min()}$ 皆需要花費 $O(\left| V \right|)$，而 $\mathrm{relax}$ 的執行次數為 $(\left| E \right|)$，所以時間複雜度為 $O(\left| V \right|^2 + \left| E \right|) = O(\left| V \right|^2)$ 2. 如果採用 binary heap ，則每次 $\mathrm{Extract-Min()}$ 皆需要花費 $O(\lg \left| V \right|)$，每次更新 heap 的 key 值也需要 $O(\lg \left| V \right|)$ (這邊指的即 $\mathrm{Decrease-Key}$)，所以時間複雜度為 $O(\left| V \right|\lg \left| V \right| + \left| E \right|\lg \left| V \right|) = \left| E \right|\lg \left| V \right|$ 3. 如果使用 [Fibonacci heap](https://hackmd.io/@RyoukiWei/fibonacci-heap) 則我們知道 $\mathrm{Decrease-Key}$ 的時間複雜度能降到 $O(1)$，所以演算法整體的時間複雜度為 $O(\left| V \right|\lg \left| V \right| + \left| E \right|)$ 我們可以整理一下 Dijkstra 中各步驟的時間複雜度，該演算法很重要： | ＼ | $\mathrm{Initialization}$ | $\mathrm{Extract-Min()}$ | $\mathrm{Decrease-Key}$ | Total | | :---: | :---: | :---: | :---: | :---: | | Array | $\theta (\left\| V \right\|)$ | $O(\left\| V \right\|^2)$ | $O(\left\| E \right\|)$ | $O(\left\| V \right\|^2)$ | | Binary Heap | $\theta (\left\| V \right\|)$ | $O(\left\| V \right\|\lg \left\| V \right\|)$ | $O(\left\| E \right\|\lg \left\| V \right\|)$ | $O(\left\| V \right\|\lg \left\| V \right\| + \left\| E \right\|\lg \left\| V \right\|)$ | | Fibonacci Heap | $\theta (\left\| V \right\|)$ | $O(\left\| V \right\|\lg \left\| V \right\|)$ | $O(\left\| E \right\|)$ | $O(\left\| V \right\|\lg \left\| V \right\| + \left\| E \right\|)$ | > [!Warning] > Dijkstra's algorithm 有個限制，那就是圖上不允許有負邊 > 如果圖上有負邊，則會使此問題不具備 greedy choice property，故使 Dijkstra's algorithm 無法保證求出正確答案例如下圖情況： ```mermaid graph LR A((s)) -- [3] --> B((a)) B -- [-2] --> C((t)) A -- [2] --> C ``` 由 $s$ 到 $t$ 的最短路徑應該是 <$s$, $a$, $t$>，但使用 Dijkstra 計算出的 shortest path tree 卻為： ```mermaid graph LR A((s)) -- [3] --> B((a)) A -- [2] --> C((t)) ``` **這邊可是超重要考點** #### Path Relaxtion Property 指的是：假設 <$s = v_0, v_1, \cdots , v_k$> 為 $s$ 到 $v_k$ 的最短路徑，依 $(v_0,v_1), (v_1,v_2), \cdots , (v_{k-1},v_k)$ 的順序做 $\mathrm{relaxtion}$，過程中可穿插圖上其他邊之 $\mathrm{relaxtion}$，則最終 $v_k$ 之 shortest path estimate 必為 $s$ 到 $v_k$ 之最短路徑長這邊要證明，可以利用數學歸納法我懶，就不寫證明出來了，但建議讀者在腦中想過一遍，要是真的考出來也要寫幾個字就能開始掰完整段證明 (~~這就是數學歸納法~~) #### 額外感悟讀者如果仔細看 Dijkstra's Algo，如果覺得很像 [BFS](https://hackmd.io/@RyoukiWei/graph_1#BFS)，表示你對圖遍歷之思考有了不同的思考，恭喜 ### Bellman-Ford Algorithm 該演算法的核心在於為每一輪圖上每條邊作 $\mathrm{relaxtion}$ ```mermaid graph LR A((s)) -- D^{k-1}[j] --> B((j)) A -- D^{k-1}[i] --> C((i)) C -- w[i, j] --> B ``` 我們採用 DP 的策略，定義 $D^{k}\lbrack j \rbrack$ 表示 $s$ 走不超過 $k$ 條邊到達 $v_j$ 之 shortest path length 由上圖可知，我們在比的就是直接從 $s$ 走到 $v_j$ 比較短？還是中間多經過些點的路徑比較短？表示成遞迴關係式： $$ D^k \lbrack j \rbrack = \begin{cases} w\lbrack 0,j \rbrack && \text{ if } k=1 \\ \min \left\{ D^{k-1}\lbrack j \rbrack, \min\limits_i \left\{ D^{k-1}\lbrack i \rbrack + w\lbrack i,j \rbrack \right\} \right\} && \text{ if } k\gt 1 \end{cases} $$ 在演算法的寫法中，Bellman-Ford 還有個額外的功能，那就是能找出 negative cycle length ```cpp! bool bellmanFord(Graph &g, int s) { initializeSingleSource(g, s); for (int i = 1; i <= g.num - 1; ++i) { // for each (u, v) for (int u = 0; u < g.num; ++u) { for (int v : g.adjList[u]) { relax(g, u, v); } } } for (int u = 0; u < g.num; ++u) { for (int v : g.adjList[u]) { if (g.vertices[v].d > g.vertices[u].d + g.w(u, v)) return false; // negative cycle found } } return true; } ``` 上述寫法的時間複雜度是 $O(\left| V \right|\left| E \right|)$ negative cycle 會使最短路徑問題不 well-defined (在負環上越繞路徑越短，那你一輩子繞圈不就好了)，所以任何最短路徑問題的演算法都不允許圖上有負環不過跟 Dijkstra 不一樣，Bellman-Ford 能夠允許圖上有負邊解釋為何上面的演算法可以偵測負環： ```cpp! for (int u = 0; u < g.num; ++u) { for (int v : g.adjList[u]) { if (g.vertices[v].d > g.vertices[u].d + g.w(u, v)) return false; // negative cycle found } } ``` 這裡用到的，正是大家早就學過的三角不等式 $\forall (u,v)\in E, \delta (s,v) \le \delta (s,u) + w(u,v)$ 此三角不等式成立 $\Leftrightarrow G$ 中不含 $s$ 可達之負環 $(\Leftarrow)$: > 若 $\exists (u,v)\in E$ 使得 $\delta (s,v) \gt \delta (s,u) + w(u,v)$ > 令 $P$ 為 $s$ 到 $u$ 之最短路徑則 $P$ 再加上 $(u,v)$ 形成 $s$ 到 $v$ 之路徑 $P'$ ，且 $w(P') = \delta (s,u) + w(u,v) \lt \delta(s,v)$ > 此與 $\delta(s,v)$ 為 $s$ 到 $v$ 之最短距離矛盾，故三角不等式成立 $(\Rightarrow)$: > 假設 $C =$ <$v_0,v_1,\cdots , v_k$> 為 $s$ 可達之 cycle，其中 $v_0=v_k$ > $\because \delta (s,v_{i+1}) \gt \delta (s,v_i) + w(v_i,v_{i+1})$ > $\Rightarrow w(v_i,v_{i+1}) \ge \delta (s,v_{i+1}) - \delta (s,v_i), i = 0,\cdots ,k-1$ > $\Rightarrow w(C) = \sum\limits_{i=0}^{k-1}w(v_i,v_{i+1}) \ge \sum\limits_{i=0}^{k-1}\left[ \delta (s,v_{i+1}) - \delta (s,v_i) \right]= \delta (s,v_k)- \delta (s,v_0)=0$ > $\therefore G$ 中不含 $s$ 可達之負環那如果你只是要用 DP 的寫法，以下是 $O(\left| V \right|^3)$ 的寫法： ```cpp! std::vector<std::vector<int>> bellmanFordDP(const Graph &g, int s) { std::vector<std::vector<int>> dp(g.num + 1, std::vector<int>(g.num, INT_MAX)); dp[0][s] = 0; for (int k = 1; k <= g.num; ++k) { for (int j = 0; j < g.num; ++j) { dp[k][j] = dp[k - 1][j]; for (int i = 0; i < g.num; ++i) { if (dp[k - 1][i] != INT_MAX && g.w(i, j) != INT_MAX) dp[k][j] = std::min(dp[k][j], dp[k - 1][i] + g.w(i, j)); } } } return dp; } ``` DP 基本只要能寫出遞迴式，就能寫出 code #### System of Difference Constraints 這是一題看似跟圖論無關，但卻能用 Bellman-Ford 解出來的題目交大 102 的資演： ([試題來源](https://eecsmt.com/graduate-school/exam/102-nctu-cs/)) ![image](https://hackmd.io/_uploads/SJDi0SL81l.png) 我們可以建立 constraint graph $G = (V,E)$ 配上 weight function $w: E \rightarrow \mathbb{R}$ $V = {v_0,v_1,\cdots ,v_5}$ 其中 $v_1,\cdots ,v_5$ 對應 $x_1,\cdots ,x_5$ 讓 $v_0$ 到各頂點的距離為 $0$，而上面的不等式就當作對應兩頂點的距離如果 Bellman-Ford 偵測出負環，此系統無解；若沒有，則我們會得出一組解，加上常數 $c$ 即通解圖如下： ![image](https://hackmd.io/_uploads/ByTHdpdL1g.png) ![image](https://hackmd.io/_uploads/BkTMKa_81g.png) 對圖使用 Bellman-Ford algorithm ```cpp! #include <iostream> #include <vector> #include <climits> struct Edge { int from, to, weight; }; struct Graph { int num; std::vector<Edge> edges; explicit Graph(int n) : num(n) {} void addEdge(int u, int v, int w) { edges.push_back({u, v, w}); } }; std::vector<int> bellmanFord(Graph &g, int s) { std::vector<int> d(g.num, INT_MAX); d[s] = 0; for (int i = 1; i < g.num; ++i) { for (const auto &edge : g.edges) { if (d[edge.from] != INT_MAX && d[edge.from] + edge.weight < d[edge.to]) d[edge.to] = d[edge.from] + edge.weight; } } // Check for negative-weight cycles for (const auto &edge : g.edges) { if (d[edge.from] != INT_MAX && d[edge.from] + edge.weight < d[edge.to]) { std::cerr << "No solution. Negative-weight cycle detected.\n"; exit(1); } } return d; } int main() { Graph g(6); // Add edges from virtual source v0 to all other vertices for (int i = 1; i <= 5; ++i) { g.addEdge(0, i, 0); // v0 -> vi with weight 0 } g.addEdge(2, 1, 1); // x1 - x2 <= 1 g.addEdge(5, 1, -1); // x1 - x5 <= -1 g.addEdge(5, 2, 1); // x2 - x5 <= 1 g.addEdge(1, 3, 15); // x3 - x1 <= 15 g.addEdge(1, 4, 4); // x4 - x1 <= 4 g.addEdge(3, 4, -1); // x4 - x3 <= -1 g.addEdge(3, 5, -3); // x5 - x3 <= -3 g.addEdge(4, 5, 0); // x5 - x4 <= 0 // Run Bellman-Ford from s = v0 auto distances = bellmanFord(g, 0); std::cout << "The general solution is:\n("; for (int i = 1; i <= 5; ++i) { std::cout << distances[i] << " + c"; if (i != 5) std::cout << ", "; } std::cout << ")\n"; return 0; } ``` ![image](https://hackmd.io/_uploads/BkTblnULye.png) ## All-pairs Shortest Path Problem 顧名思義，其實就是 single-source 但變成每個頂點都當過 source 如過圖沒有負邊，那我們就對每個頂點做 Dijkstra 就好 (做 $\left| V \right|$ 次)，時間複雜度頂多 $O(\left| V \right|^3)$ 如果要能處理負邊而使用 Bellman-Ford 呢？那時間複雜度會是 $O(\left| V \right|^4)$ 那有沒有能處理負邊又在 $O(\left| V \right|^3)$ 的演算法呢？有的。 ### Floyd-Warshall Algorithm Floyd-Washall 也是採用 DP 策略給定 $G = (V,E)$ 為不含有負環的有向圖，$V = \left\{ 1,2,\cdots ,n \right\}$ ， $w: E\rightarrow \mathbb{R}$ 為 weight function 使用 [adjacency matrix](https://hackmd.io/@RyoukiWei/graph_1#Adjacency-Matrix) $W = \lbrack w_{ij} \rbrack$ 來表示圖，其中 $$ w_{ij} = \begin{cases} 0 &&\text{ if } i=j \\ w(i,j) &&\text{ if } i\neq j \text{ and } (i,j)\in E \\ \infty &&\text{ if } i\neq j \text{ and } (i,j)\notin E \end{cases} $$ 再定義 $D = \lbrack d_{ij} \rbrack, d_{ij} = \delta (i,j)$， $\Pi = \lbrack \pi_{ij} \rbrack, \pi_{ij}$ 為 $i$ 到 $j$ 之某個最短路徑中 $j$ 的 predecessor 若 $v$ 為路徑 $P$ 中的某點但不為兩端點，則稱 $v$ 為 $P$ 之 intermediate vertex (中繼點) 令 $d_{ij}^{(k)}$ 為 $i$ 到 $j$ 且途中只允許經過 $1,\cdots ,k$ 之最短路徑 $P$ 的長度： 1. 若 $P$ 中不含 $k$ ：此時 $d_{ij}^{(k)} = d_{ij}^{(k-1)}$ 2. 若 $P$ 中包含 $k$ ：因為一定要過 $k$ ，我們可以寫成 $d_{ij}^{(k)} = d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$ 經過上述討論，我們可以整理出 $d_{ij}^{(k)}$ 之遞迴關係式： $$ d_{ij}^{(k)} = \begin{cases} w_{ij} && \text{ if } k = 0\\ \min\left\{ d_{ij}^{(k-1)},d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right\} && \text { if } k \ge 1 \end{cases} $$ 而計算 predecessor 之遞迴關係式： $$ \pi_{ij}^{k} = \begin{cases} \mathrm{NIL} && \text{ if } k=0 \text{ and } (i=j\vee w_{ij} = \infty) \\ i && \text{ if } k=0 \text{ and } (i\neq j\vee w_{ij} \lt \infty) \\ \pi_{ij}^{k-1} && \text{ if } d_{ij}^{(k-1)} \le d_{ik}^{(k-1)} + d_{kj}^{(k-1)} \\ \pi_{kj}^{k-1} && \text{ if } d_{ij}^{(k-1)} \gt d_{ik}^{(k-1)} + d_{kj}^{(k-1)} \end{cases} $$ ```cpp! std::vector<std::vector<int>> floydWarshall(const std::vector<std::vector<int>> &W) { const int n = W.size(); auto D = W; 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] != INT_MAX && D[k][j] != INT_MAX) D[i][j] = std::min(D[i][j], D[i][k] + D[k][j]); } } } return D; } ``` 例如給你一張圖： ```mermaid graph LR A((1)) -- [6] -->B((2)) B -- [2] --> C((3)) A -- [-1] --> C B -- [2] --> A C -- [3] --> B ``` 執行演算法的過程應該會是： ![image](https://hackmd.io/_uploads/HyBa8T8Ukl.png) 考試時沒辦法打 code 讓電腦執行，所以值得記憶如何加速手寫操作 ![image](https://hackmd.io/_uploads/Syv9DaLU1e.png) 上圖中螢光筆標記的代表下回合依舊保持不變的部份，我們計算剩下的部份就好這樣看會快很多 #### Transtive Closure Floyd-Warshall 可以拿來解遞移閉包的問題，改一下就好： $$ t_{ij}^{(k)} = \begin{cases} 0 && \text{ if } k = 0, i\neq j \text{ and } (i,j)\notin E \\ 1 && \text{ if } k = 0, i = j \text{ and } (i,j)\in E \\ t_{ij}^{(k-1)}\vee (t_{ik}^{(k-1)}\wedge t_{kj}^{(k-1)}) && \text { if } k \ge 1 \end{cases} $$ 我們處理的就會變成是關係矩陣這邊比較是離散的內容，詳細可見[這裡](https://hackmd.io/@RyoukiWei/binary-relation#Closure) 例題可以參考[ LeetCode 1462. Course Schedule IV](https://hackmd.io/@RyoukiWei/leetcode1462) ### Johnson's Algorithm Floyd-Warshall 的確厲害，但要是沒有負邊的話，感覺 Dijkstra 能有更好的表現如果我們可以調整圖上的權重，使得圖上不存在負邊，那麼我們執行 $\left| V \right|$ 次 Dijkstra 即可解 all-pairs shortest path problem 啦 $G$ 為 sparse 且使用 Fibonacci heap 的話，此方法的時間複雜度比 Floyd-Warshall 更好然而，此演算法困難也是其厲害的點，就在於如何 reweight 我們必須保證以下三點成立： 1. reweight 後的最短路徑仍會是原圖的最短路徑 2. 原圖不含負環，則 reweight 後也不應該產生負環 3. reweight 後所有邊皆非負我們再用更數學的角度審視要滿足的條件假設 $G = (V,E)$ 為 directed weighted graph，其 weight function 為 $w: E\rightarrow \mathbb{R}$ 令 $\hat{w}: E\rightarrow \mathbb{R}$ 為新的 weight function 假設 $(u,v)$ 在 reweight 後的最短路徑為 $\delta (u,v)$ 定義 $\hat{h}: V\rightarrow \mathbb{R}$ ： $$ \hat{w}(u,v) = w(u,v)+h(u)-h(v) $$ $\forall (u,v)\in E$ ，$\hat{w}$ 滿足： 1. 若 $P$ 為 $G$ 中 $u$ 到 $v$ 的路徑，則 $\hat{w}(P) = w(P) + h(u)-h(v)$ 2. 若 $C$ 為 $G$ 中的 cycle ，則 $\hat{w}(C) = w(C)$ 我們目標是使 $\hat{w}(u,v) = w(u,v)+h(u)-h(v) \ge 0, \forall (u,v)\in E$ 我們前面就知道了，在不含負環的情況下，三角不等式 $w(u,v) + \delta (s,u) \ge \delta (s,v)$ 必成立所以我們的作法即在 $G$ 中加入頂點 $s$ ，$s$ 連到所有頂點，並且這些邊的 weight 皆為 $0$ $\hat{w}(u,v) = w(u,v)+\delta (s,u)- \delta(s,v)\ge 0$ 必成立所以我們就定義 $\hat{w}: E \rightarrow \mathbb{R}$ $$ \hat{w}(u,v) = w(u,v)+\delta (s,u)- \delta(s,v), \forall (u,v)\in E $$ ```cpp! void johnson(Graph &g) { Graph gNew(g.num + 1); for (int u = 0; u < g.num; ++u) { for (int v : g.adjList[u]) { gNew.addEdge(u, v, g.w(u, v)); } gNew.addEdge(g.num, u, 0); // extra vertex s } if (!bellmanFord(gNew, g.num)) { std::cerr << "Negative cycle detected!\n"; return; } for (int u = 0; u < g.num; ++u) { for (int v : g.adjList[u]) { g.edgeWeights[{u, v}] = g.w(u, v) + gNew.vertices[u].d - gNew.vertices[v].d; } } for (int u = 0; u < g.num; ++u) { dijkstra(g, u); } } ``` Time complexity: $O(\left| V \right|\left| E \right| + \left| V \right|^2\lg \left| V \right|)$ ## 【資工考研】DSA: Graph 全系列 - [【資工考研】DSA: Graph (1)](https://hackmd.io/@RyoukiWei/graph_1) - [【資工考研】DSA: Graph (3)](https://hackmd.io/@RyoukiWei/graph_3)