owned this note changed 11 days ago
Published Linked with GitHub

Shortest Path最短路徑

3/6


什麼是最短路徑?

通常會有一張圖,要你算從起點\(s\)走到終點\(t\)所需的最小時間or花費


像是4走到5的時間/花費是4
或是2走到3的時間/花費是7
image


圖也有分有向圖和無向圖
image


或是有負環或是沒負環
image

在最短路徑這個演算法上我們要對應不同的圖
使用合適的演算法


存圖技巧

  • 鄰接矩陣
  • 鄰接串列

鄰接矩陣

image

5 <-> 6 花費為 9
matrix[5][6] = matrix[6][5] = 9


鄰接矩陣存圖

  • 有向
int dis[N][N];
void add_edge(int u,int v,int w){//起點u、終點v、權重w
    dis[u][v]=w;
}
  • 無向
int dis[N][N];
void add_edge(int u,int v,int w){//連接u和v、權重whttps://hackmd.io/_uploads/BytUT8996.png
    dis[u][v]=w;
    dis[v][u]=w;
}

鄰接串列

1 -> 3 權重為 5
表示為 1 : {3, 5}

image


鄰接串列存圖

  • 有向
vector<pair<int,int>>graph[N];//pair存{終點,權重}
void add_edge(int u,int v,int w){//起點u、終點v、權重w
    graph[u].push_back({v,w});
}
  • 無向
vector<pair<int,int>>graph[N];//pair存{終點,權重}
void add_edge(int u,int v,int w){//連接u和v、權重w
    graph[u].push_back({v,w});
    graph[v].push_back({u,w});
}

最短路徑分類

  • 單源最短路徑(固定起點、不固定終點)
  • 全點對最短路徑(不固定起點、不固定終點)

單源最短路徑

給你一個圖,一個起點,求出這個起點到每個點的最短路徑


全點對最短路徑

給你一個圖,多組起點和終點,求出每組起點到終點的最短路徑
image


演算法們

  • 單源最短路徑
    • Dijkstra
    • Bellman-Ford
  • 全點對最短路徑
    • Floyd-warshall

Dijkstra


想法

由於是單源最短路徑,所以會先創一個陣列,這裡叫dis

一開始會把dis[起點]設為0,代表起點到自己的距離是0

然後把dis[其他點]設為INF,再重複做下面的步驟

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點\(u\)設定為走過
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

什麼是鬆弛

假設 dis[u][v] = x,如果存在一個點e
使得x > dis[u][e] + dis[e][v]
那麼我們可以更新dis[u][v] = dis[u][e] + dis[e][v]
這樣子我們稱透過e進行了一次鬆弛


dis[2][3] = 5
因為 dis[2][3] > dis[2][1] + dis[1][3] (5 > 4)
我們更新 dis[2][3] = 4
image


學會鬆弛之後我們就可以看看Dijkstra在做什麼了
假設一開始起點是2,要算下圖的最短距離

image


初始化

先把dis初始化,把起點設為0,其他設為INF(很大的數字)

image

dis visited
1 INF 0
2 0 0
3 INF 0
4 INF 0
5 INF 0
6 INF 0

  1. 選一個離起點最近並且沒有走過的點u \(\to\) 選2
  2. 把點\(u\)設定為走過
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 INF 0
2 0 0
3 INF 0
4 INF 0
5 INF 0
6 INF 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點u設定為走過 \(\to\) visited[2]=1
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 INF 0
2 0 1
3 INF 0
4 INF 0
5 INF 0
6 INF 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點\(u\)設定為走過
  3. 透過所有連接點u和v的邊,去鬆弛點v

image

dis visited
1 INF 0
2 0 1
3 INF 0
4 INF 1 0
5 INF 0
6 INF 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點\(u\)設定為走過
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 INF 0
2 0 1
3 INF 0
4 1 0
5 INF 0
6 7 0

  1. 選一個離起點最近並且沒有走過的點u \(\to\) 選4
  2. 把點\(u\)設定為走過
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 INF 0
2 0 1
3 INF 0
4 1 0
5 INF 0
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點u設定為走過 \(\to\) visited[4]=1
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 INF 0
2 0 1
3 INF 0
4 1 1
5 INF 0
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點\(u\)設定為走過
  3. 透過所有連接點u和v的邊,去鬆弛點v

image

dis visited
1 INF 5 0
2 0 1
3 INF 2 0
4 1 1
5 INF 5 0
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點\(u\)設定為走過
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 5 0
2 0 1
3 2 0
4 1 1
5 5 0
6 7 0

  1. 選一個離起點最近並且沒有走過的點u \(\to\) 選3
  2. 把點\(u\)設定為走過
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 5 0
2 0 1
3 2 0
4 1 1
5 5 0
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點u設定為走過 \(\to\) visited[3]=1
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 5 0
2 0 1
3 2 1
4 1 1
5 5 0
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點\(u\)設定為走過
  3. 透過所有連接點u和v的邊,去鬆弛點v

image

dis visited
1 5 0
2 0 1
3 2 1
4 1 1
5 5 4 0
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點\(u\)設定為走過
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 5 0
2 0 1
3 2 1
4 1 1
5 4 0
6 7 0

  1. 選一個離起點最近並且沒有走過的點u \(\to\) 選5
  2. 把點\(u\)設定為走過
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 5 0
2 0 1
3 2 1
4 1 1
5 4 0
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點u設定為走過 \(\to\) visited[5]=1
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 5 0
2 0 1
3 2 1
4 1 1
5 4 1
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點\(u\)設定為走過
  3. 透過所有連接點u和v的邊,去鬆弛點v

image

dis visited
1 5 0
2 0 1
3 2 1
4 1 1
5 4 1
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點\(u\)設定為走過
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 5 0
2 0 1
3 2 1
4 1 1
5 4 1
6 7 0

  1. 選一個離起點最近並且沒有走過的點u \(\to\) 選1
  2. 把點\(u\)設定為走過
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 5 0
2 0 1
3 2 1
4 1 1
5 4 1
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點u設定為走過 \(\to\) visited[1]=1
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 5 1
2 0 1
3 2 1
4 1 1
5 4 1
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點\(u\)設定為走過
  3. 透過所有連接點u和v的邊,去鬆弛點v

image

dis visited
1 5 1
2 0 1
3 2 1
4 1 1
5 4 1
6 7 0

  1. 選一個離起點最近並且沒有走過的點u \(\to\) 選6
  2. 把點\(u\)設定為走過
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 5 1
2 0 1
3 2 1
4 1 1
5 4 1
6 7 0

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點u設定為走過 \(\to\) visited[1]=1
  3. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\)

image

dis visited
1 5 1
2 0 1
3 2 1
4 1 1
5 4 1
6 7 1

  1. 選一個離起點最近並且沒有走過的點\(u\)
  2. 把點\(u\)設定為走過
  3. 透過所有連接點u和v的邊,去鬆弛點v

image

dis visited
1 5 1
2 0 1
3 2 1
4 1 1
5 4 1
6 7 1

這樣就走完ㄌ

image

dis visited
1 5 1
2 0 1
3 2 1
4 1 1
5 4 1
6 7 1

分析一下可能的複雜度,以下假設\(V\)為點個數,\(E\)為邊個數

  1. 初始化 \(\to\) \(O(V)\)
  2. 選一個離起點最近並且沒有走過的點\(u\) \(\to\) \(O(V \cdot V)\)
  3. 把點\(u\)設定為走過 \(\to\) \(O(V \cdot 1)\)
  4. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\) \(\to\) \(O(E)\)

總複雜度:\(O(V^2+E)\)


來看這個例題

給你一個圖,圖上有\(V\)個點,\(E\)條邊,給定起點問你這個起點到每個點的最短距離。
\(1 \le V\le10^5\)\(1 \le E\le 2\cdot 10^5\)


顯然剛剛的做法砸下去就會過了,那複雜度呢?

\(O(V^2+E)\) \(\to\) \(O(10^{10})\) \(\to\) TLE


看看有哪些步驟的複雜度是可以被優化掉的

  1. 初始化 \(\to\) \(O(V)\)
  2. 選一個離起點最近並且沒有走過的點\(u\) \(\to\) \(O(V \cdot V)\)
  3. 把點\(u\)設定為走過 \(\to\)\(O(V \cdot 1)\)
  4. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\) \(\to\) \(O(E)\)

總複雜度:\(O(V^2+E)\)

因為\(V^2\)太大,我們嘗試把\(V^2\)優化掉


目標 : 選一個離起點最近並且沒有走過的點u

代表我們需要選一個點u,他的dis[u]要最小,而且vis = 0

大家可以想一下要怎麼樣比\(O(V)\)還要快選到這個點\(u\)


我們可用到priority_queue,他可以在\(O(\log_2 n)\)的時間復雜度內找到最小/大的值

透過這個 \(O(V * V)\) -> \(O(V\log_2 V)\) (\(10^{10}\) -> \(1.6 \times 10^6\))

很明顯這樣複雜度就好了


總複雜度

  1. 初始化 \(\to\) \(O(V)\)
  2. 選一個離起點最近並且沒有走過的點\(u\) \(\to\) \(O(V \cdot logV)\)
  3. 把點\(u\)設定為走過 \(\to\)\(O(V \cdot 1)\)
  4. 透過所有連接點\(u\)\(v\)的邊,去鬆弛點\(v\) \(\to\) \(O(E)\)

總複雜度:\(O(VlogV+E)\)


若是邊權只有0或1,有沒有更好的優化方式?


使用deque取代priority_queue。
可以發現我們只要維持每次取出最小值
所以邊權為0我們就把他push_front()
邊權為1我們就把他push_back()
這樣可以保持deque內的單調性質
選一個離起點最近並且沒有走過的點的複雜度從 \(O(logV)\) 再次降低到 \(O(1)\)
這個技巧以後應該還會提到 叫做 \(0-1BFS\)


實作

我們在priority_queue存入一個pair<int, int>
第一維存dis
第二維存點id
因為pair優先照第一維排序,所以取出來的會是dis最小的

priority_queue<pii, vector<pii>, greater<pii>> pq;

範例code:

vector<pair<int, int>> E[V]; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q; vector<int> dis[N]; Q.emplace(0, 起點); while(Q.size()) { auto [du, u] = Q.top(); Q.pop(); // 取出當前最近的點 if(dis[u].size() >= 1) continue; // 這個等於已經vis過的點 (已經算出距離) dis[u].push_back(du); // 算出距離 for(auto [v, w] : E[u]) Q.emplace(w + du, v); }

0-1BFS

vector<pair<int, int>> E[V]; vector<int> dis[N]; deque<pair<int, int>> Q; Q.emplace_front(0, 起點); while(Q.size()) { auto [du, u] = Q.front(); Q.pop_front(); // 取出當前最近的點 if(dis[u].size() >= 1) continue; // 這個等於已經vis過的點 (已經算出距離) dis[u].push_back(du); // 算出距離 for(auto [v, w] : E[u]) { if (w) Q.emplace_back(w + du, v); else Q.emplace_front(w + du, v); } }

小限制

如果圖中有負權邊,Dijkstra這個演算法不能用
因為Dijkstra會取dis最小的點,在有負權邊的情況下會爛掉


起點為1的時候會爛掉
屏幕截图 2025-02-25 003217


最短路徑樹

當你給定了一個起點,從這個起點走到任意的點的路徑會形成一棵樹(也有可能是多顆)
以下面的例子來說,最短路徑樹有兩顆
image


下課時間


Bellman-Ford


想法

Bellman-Ford是以每一條邊去做鬆弛,能鬆弛就直接去做鬆弛,直到不能鬆弛為止。
image


不難發現由於一條最短路最多會經過\(n-1\)條邊,因此只要對每個邊鬆弛\(n-1\)次就好。
image


以每一條邊去做鬆弛

for (int i = 0; i < m; i++){
    if (dis[edge[i].u] + edge[i].w < dis[edge[i].v]){
        dis[edge[i].v] = dis[edge[i].u] + edge[i].w;
    }
}

複雜度:總共\(m\)條邊,鬆弛\(n-1\)\(\to O(nm)\)


負環

可以無限減少花費的一個環 (\(1 \to 3 \to 2 \to 1\))
image


有負環的話 會發現可以無限進行鬆弛操作
image


判斷負環

若是第\(n\)輪鬆弛還有點被鬆弛到 代表這張圖存在負環


SPFA

其實是Bellman-Ford的優化版本


想法

可以發現Bellman-Ford有很多鬆弛操作是多餘的
只有上一次被鬆弛的節點,所連接的邊,才有可能引起下一次鬆弛


code

我們用一個queue來維護 [可能會引起鬆弛操作的節點]

struct edge { int v, w; }; int s, n; // 起點 點數量 vector<edge> E[MXN]; vector<int> dis(MXN, INF), cnt(MXN), inq(MXN); // cnt記錄最短路經過幾條邊 // inq記錄節點是否在queue裡面 queue<int> Q; dis[s] = 0; Q.push(s); inq[s] = 1; while (Q.size()) { int u = Q.front(); Q.pop(); inq[u] = 0; for (auto [v, w] : E[u]) { if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; cnt[v] = cnt[u] + 1; if (cnt[v] >= n) { // 有負環 因為一般最短路只會經過 n - 1 條邊 } if (!inq[v]) Q.push(v), inq[v] = 1; } } }

複雜度

在大部分時候SPFA跑的非常快
但其實最差的情況複雜度還是 \(O(nm)\)
當你發現Bellman-Ford TLE的時候
這個時候你就可以用SPFA


Floyd-warshall


定義

dp[\(k\)][\(i\)][\(j\)] \(\to\) 代表從 \(i\)\(j\) 只經過 \(1\) ~ \(k\) 的最短距


初始化

dp[\(0\)][\(i\)][\(i\)] \(\to\) 0
dp[\(0\)][\(i\)][\(j\)]
if : \(i\)\(j\) 有邊 dp[\(0\)][\(i\)][\(j\)] \(=\) 邊權
else : dp[\(0\)][\(i\)][\(j\)] = \(\infty\)


轉移

dp[\(k\)][\(x\)][\(y\)] = min(dp[\(k-1\)][\(x\)][\(y\)], dp[\(k-1\)][\(x\)][\(k\)] + dp[\(k-1\)][\(k\)][\(y\)])


實現

for (k = 1; k <= n; k++) {
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]);
    }
  }
}

空間複雜度:\(O(N^3)\)
時間複雜度:\(O(N^3)\)


空間優化

可以發現轉移的時候有一維是可以滾動掉的
dp[\(k\)][\(i\)][\(j\)] \(\to\) dp[\(i\)][\(j\)]
所以空間複雜度可以優化到 \(O(N^2)\)


Floyd-warshall可以在時間複雜度\(O(N^3)\)、空間複雜度\(O(N^2)\)以內做完全點對最短路徑問題

基本上要做全點對最短路徑一定砸Floyd-warshall


來練習0.0
題目連結

Select a repo