【資工考研】DSA: Graph (2) Shortest Path Problem

Graph Representations
BFS & DFS
Shortest Path Problem
Minimum Spanning Tree
Articulation Point
Flow Network

Shortest Path Problem

	Single-source Shortest Path			All-pairs Shortest Path
演算法	DAG	Dijkstra	Bellman-Fold	Floyd-Warshall	Johnson
策略	利用 tolopological sort	greedy	DP	DP	Dijkstra + Bellman-Fold
可否有 cycle	X	O	O	O	O
可否有negative cost edge	O	X	O	O	O
可否有negative cycle length	X	X	X	X	X

Single-source Shortest Path Problem

給定

G = (V, E)

為一 directed weighted graph，其 weight function 為

w : E \to R

令

w (P)

為 path

P

上所有邊之權重和，稱之為

P

之權重

$\forall u, v \in V$ 定義
$δ (u, v)$ 為所有自
$u$ 到
$v$ 的路徑中權重最小者，若
$u$ 無法抵達
$v$ 則
$δ (u, v) = \infty$
若
$P$ 為一條自
$u$ 到
$v$ 的 path 滿足
$w (P) = δ (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 . π

\forall v \in V

，

v . d

表示

s

到

v

之 shortest path esimate，在最短路徑演算法中，此值會被不斷更新，直到演算法執行結束時方為

s

到

v

之最短路徑長

定義幾個副程式

先調整一下 Graph：

// 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 ∞
    }
};

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

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 (| V | + | E |)

另外，在 DAG 上求最長路徑 (又稱 critical path) 有至少兩種 linear time 的作法：

把上面最短路徑演算法中， relax 裡面所有
$\infty$ 改成
$- \infty$ 並把
$>$ 改成
$<$
把 DAG 中所有邊權重乘
$- 1$ ，因為沒有 cycle 的關係，不用擔心會出現 negative cycle

Dijkstra's Algorithm

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

用來蒐集已經計算出最短距離的頂點
每次

Extract - Min ()

完，將

u

加入其中 (

S = S \cup {u}

)
不過這不影響到演算法本身的表達

Dijkstra 最重要的靈魂就在於那個 priority queue
我們使用該資料結構來每回合選出 shortest path estimate 最小的頂點

u

本演算法的時間複雜度會受選擇怎樣的資料結構來作為 priority queue 影響：

演算法中的 while 執行次數為

O (| V |)

，故

如果我們是利用一個大小為
$| V |$ 的陣列，則每次
$Extract - Min ()$ 皆需要花費
$O (| V |)$ ，而
$relax$ 的執行次數為
$(| E |)$ ，所以時間複雜度為
$O ({| V |}^{2} + | E |) = O ({| V |}^{2})$
如果採用 binary heap ，則每次
$Extract - Min ()$ 皆需要花費
$O (\lg | V |)$ ，每次更新 heap 的 key 值也需要
$O (\lg | V |)$ (這邊指的即
$Decrease - Key$ )，所以時間複雜度為
$O (| V | \lg | V | + | E | \lg | V |) = | E | \lg | V |$
如果使用 Fibonacci heap 則我們知道
$Decrease - Key$ 的時間複雜度能降到
$O (1)$ ，所以演算法整體的時間複雜度為
$O (| V | \lg | V | + | E |)$

我們可以整理一下 Dijkstra 中各步驟的時間複雜度，該演算法很重要：

＼	$Initialization$	$Extract - Min ()$	$Decrease - Key$	Total
Array	$θ (\| V \|)$	$O ({\| V \|}^{2})$	$O (\| E \|)$	$O ({\| V \|}^{2})$
Binary Heap	$θ (\| V \|)$	$O (\| V \| \lg \| V \|)$	$O (\| E \| \lg \| V \|)$	$O (\| V \| \lg \| V \| + \| E \| \lg \| V \|)$
Fibonacci Heap	$θ (\| V \|)$	$O (\| V \| \lg \| V \|)$	$O (\| E \|)$	$O (\| V \| \lg \| V \| + \| E \|)$

Warning

Dijkstra's algorithm 有個限制，那就是圖上不允許有負邊
如果圖上有負邊，則會使此問題不具備 greedy choice property，故使 Dijkstra's algorithm 無法保證求出正確答案

例如下圖情況：

由

s

到

t

的最短路徑應該是 <

s

a

t

>，但使用 Dijkstra 計算出的 shortest path tree 卻為：

這邊可是超重要考點

Path Relaxtion Property

指的是：假設 <

s = v_{0}, v_{1}, \dots, v_{k}

> 為

s

到

v_{k}

的最短路徑，依

(v_{0}, v_{1}), (v_{1}, v_{2}), \dots, (v_{k - 1}, v_{k})

的順序做

relaxtion

，過程中可穿插圖上其他邊之

relaxtion

，則最終

v_{k}

之 shortest path estimate 必為

s

到

v_{k}

之最短路徑長

這邊要證明，可以利用數學歸納法
我懶，就不寫證明出來了，但建議讀者在腦中想過一遍，要是真的考出來也要寫幾個字就能開始掰完整段證明 (~~這就是數學歸納法~~)

額外感悟

讀者如果仔細看 Dijkstra's Algo，如果覺得很像 BFS，表示你對圖遍歷之思考有了不同的思考，恭喜

Bellman-Ford Algorithm

該演算法的核心在於為每一輪圖上每條邊作

relaxtion

我們採用 DP 的策略，定義

D^{k} [j]

表示

s

走不超過

k

條邊到達

v_{j}

之 shortest path length
由上圖可知，我們在比的就是直接從

s

走到

v_{j}

比較短？還是中間多經過些點的路徑比較短？

表示成遞迴關係式：

D^{k} [j] = {\begin{cases} w [0, j] & if k = 1 \\ min {D^{k - 1} [j], min_{i} {D^{k - 1} [i] + w [i, j]}} & if k > 1 \end{cases}

在演算法的寫法中，Bellman-Ford 還有個額外的功能，那就是能找出 negative cycle length

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 (| V | | E |)

negative cycle 會使最短路徑問題不 well-defined (在負環上越繞路徑越短，那你一輩子繞圈不就好了)，所以任何最短路徑問題的演算法都不允許圖上有負環
不過跟 Dijkstra 不一樣，Bellman-Ford 能夠允許圖上有負邊

解釋為何上面的演算法可以偵測負環：

    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, δ (s, v) \leq δ (s, u) + w (u, v)

此三角不等式成立

\Leftrightarrow G

中不含

s

可達之負環

(\Leftarrow)

若
$\exists (u, v) \in E$ 使得
$δ (s, v) > δ (s, u) + w (u, v)$
令
$P$ 為
$s$ 到
$u$ 之最短路徑則
$P$ 再加上
$(u, v)$ 形成
$s$ 到
$v$ 之路徑
$P^{'}$ ，且
$w (P^{'}) = δ (s, u) + w (u, v) < δ (s, v)$
此與
$δ (s, v)$ 為
$s$ 到
$v$ 之最短距離矛盾，故三角不等式成立

(\Rightarrow)

假設
$C =$ <
$v_{0}, v_{1}, \dots, v_{k}$ > 為
$s$ 可達之 cycle，其中
$v_{0} = v_{k}$

$∵ δ (s, v_{i + 1}) > δ (s, v_{i}) + w (v_{i}, v_{i + 1})$

$\Rightarrow w (v_{i}, v_{i + 1}) \geq δ (s, v_{i + 1}) - δ (s, v_{i}), i = 0, \dots, k - 1$

$\Rightarrow w (C) = \sum_{i = 0}^{k - 1} w (v_{i}, v_{i + 1}) \geq \sum_{i = 0}^{k - 1} [δ (s, v_{i + 1}) - δ (s, v_{i})] = δ (s, v_{k}) - δ (s, v_{0}) = 0$

$∴ G$ 中不含
$s$ 可達之負環

那如果你只是要用 DP 的寫法，以下是

O ({| V |}^{3})

的寫法：

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 的資演： (試題來源)

我們可以建立 constraint graph

G = (V, E)

配上 weight function

w : E \to R

V = v_{0}, v_{1}, \dots, v_{5}

其中

v_{1}, \dots, v_{5}

對應

x_{1}, \dots, x_{5}

讓

v_{0}

到各頂點的距離為

0

，而上面的不等式就當作對應兩頂點的距離

如果 Bellman-Ford 偵測出負環，此系統無解；若沒有，則我們會得出一組解，加上常數

c

即通解

圖如下：

對圖使用 Bellman-Ford algorithm

#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;
}

All-pairs Shortest Path Problem

顧名思義，其實就是 single-source 但變成每個頂點都當過 source

如過圖沒有負邊，那我們就對每個頂點做 Dijkstra 就好 (做

| V |

次)，時間複雜度頂多

O ({| V |}^{3})

如果要能處理負邊而使用 Bellman-Ford 呢？那時間複雜度會是

O ({| V |}^{4})

那有沒有能處理負邊又在

O ({| V |}^{3})

的演算法呢？有的。

Floyd-Warshall Algorithm

Floyd-Washall 也是採用 DP 策略

給定

G = (V, E)

為不含有負環的有向圖，

V = {1, 2, \dots, n}

，

w : E \to R

為 weight function

使用 adjacency matrix

W = [w_{i j}]

來表示圖，其中

w_{i j} = {\begin{cases} 0 & if i = j \\ w (i, j) & if i \neq j and (i, j) \in E \\ \infty & if i \neq j and (i, j) \notin E \end{cases}

再定義

D = [d_{i j}], d_{i j} = δ (i, j)

，

Π = [π_{i j}], π_{i j}

為

i

到

j

之某個最短路徑中

j

的 predecessor
若

v

為路徑

P

中的某點但不為兩端點，則稱

v

為

P

之 intermediate vertex (中繼點)

令

d_{i j}^{(k)}

為

i

到

j

且途中只允許經過

1, \dots, k

之最短路徑

P

的長度：

若
$P$ 中不含
$k$ ：此時
$d_{i j}^{(k)} = d_{i j}^{(k - 1)}$
若
$P$ 中包含
$k$ ：因為一定要過
$k$ ，我們可以寫成
$d_{i j}^{(k)} = d_{i k}^{(k - 1)} + d_{k j}^{(k - 1)}$

經過上述討論，我們可以整理出

d_{i j}^{(k)}

之遞迴關係式：

d_{i j}^{(k)} = {\begin{cases} w_{i j} & if k = 0 \\ min {d_{i j}^{(k - 1)}, d_{i k}^{(k - 1)} + d_{k j}^{(k - 1)}} & if k \geq 1 \end{cases}

而計算 predecessor 之遞迴關係式：

π_{i j}^{k} = {\begin{cases} NIL & if k = 0 and (i = j \lor w_{i j} = \infty) \\ i & if k = 0 and (i \neq j \lor w_{i j} < \infty) \\ π_{i j}^{k - 1} & if d_{i j}^{(k - 1)} \leq d_{i k}^{(k - 1)} + d_{k j}^{(k - 1)} \\ π_{k j}^{k - 1} & if d_{i j}^{(k - 1)} > d_{i k}^{(k - 1)} + d_{k j}^{(k - 1)} \end{cases}

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;
}

例如給你一張圖：

執行演算法的過程應該會是：

考試時沒辦法打 code 讓電腦執行，所以值得記憶如何加速手寫操作

上圖中螢光筆標記的代表下回合依舊保持不變的部份，我們計算剩下的部份就好
這樣看會快很多

Transtive Closure

Floyd-Warshall 可以拿來解遞移閉包的問題，改一下就好：

t_{i j}^{(k)} = {\begin{cases} 0 & if k = 0, i \neq j and (i, j) \notin E \\ 1 & if k = 0, i = j and (i, j) \in E \\ t_{i j}^{(k - 1)} \lor (t_{i k}^{(k - 1)} \land t_{k j}^{(k - 1)}) & if k \geq 1 \end{cases}

我們處理的就會變成是關係矩陣

這邊比較是離散的內容，詳細可見這裡

例題可以參考 LeetCode 1462. Course Schedule IV

Johnson's Algorithm

Floyd-Warshall 的確厲害，但要是沒有負邊的話，感覺 Dijkstra 能有更好的表現

如果我們可以調整圖上的權重，使得圖上不存在負邊，那麼我們執行

| V |

次 Dijkstra 即可解 all-pairs shortest path problem 啦

G

為 sparse 且使用 Fibonacci heap 的話，此方法的時間複雜度比 Floyd-Warshall 更好

然而，此演算法困難也是其厲害的點，就在於如何 reweight
我們必須保證以下三點成立：

reweight 後的最短路徑仍會是原圖的最短路徑
原圖不含負環，則 reweight 後也不應該產生負環
reweight 後所有邊皆非負

我們再用更數學的角度審視要滿足的條件

假設

G = (V, E)

為 directed weighted graph，其 weight function 為

w : E \to R

令

\hat{w} : E \to R

為新的 weight function
假設

(u, v)

在 reweight 後的最短路徑為

δ (u, v)

定義

\hat{h} : V \to R

：

\hat{w} (u, v) = w (u, v) + h (u) - h (v)

\forall (u, v) \in E

，

\hat{w}

滿足：

若
$P$ 為
$G$ 中
$u$ 到
$v$ 的路徑，則
$\hat{w} (P) = w (P) + h (u) - h (v)$
若
$C$ 為
$G$ 中的 cycle ，則
$\hat{w} (C) = w (C)$

我們目標是使

\hat{w} (u, v) = w (u, v) + h (u) - h (v) \geq 0, \forall (u, v) \in E

我們前面就知道了，在不含負環的情況下，三角不等式

w (u, v) + δ (s, u) \geq δ (s, v)

必成立
所以我們的作法即在

G

中加入頂點

s

，

s

連到所有頂點，並且這些邊的 weight 皆為

0

\hat{w} (u, v) = w (u, v) + δ (s, u) - δ (s, v) \geq 0

必成立

所以我們就定義

\hat{w} : E \to R

\hat{w} (u, v) = w (u, v) + δ (s, u) - δ (s, v), \forall (u, v) \in E

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);
    }
}