最短路徑 shortest path

甚麼是最短路徑？

給定一個帶權圖及點 l, r，求點 l 走到點 r 的最小路徑權重和。

設一圖：

其中要求第

$1$ 點和第

$3$ 點的最短路徑，那麼答案就是：

$3+1=4\Rightarrow 4$

演算法：發展期

shortest path 一開始時，大家想出的是複雜度較高的算法，但都是後來複雜度較低演算法的基礎。

其中一個大概念是鬆弛 (Relaxation)

設有一圖：

我們可以得知：從第

$2$ 點到第

$3$ 點，如果只走一條路，則長度為

$8$。

但若找到一點

$k$，使

$dis(2,k)+dis(k,3)<dis(2,3)$，則答案會縮小，更接近最短路徑解。如下圖例子：

此技巧即鬆弛，且我們能得知：

$min(dis(2,3))\le 6$ (因為鬆弛是可以進行很多次的)

Floyd-Warshall 演算法

這個演算法就是將所有點對其他點都鬆弛過，那麼找到的路徑解即最短路徑。

int n, rd, l, r, v;
cin >> n >> rd;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 1e9));
for(int i = 0; i < rd; i++){
    cin >> l >> r >> v;
    dp[l][r] = dp[r][l] = v;
    //每條路皆雙向 
}

//以下即 Floyd-Warshall
for(int k = 1; i <= n; i++){
    for(int i = 1; j <= n; j++){
        for(int j = 1; k <= n; k++){
            dp[i][j] = min(dp[i][k] + dp[k][j] , dp[i][j]);
            //窮舉所有鬆弛可能
        }
    }
}
cin >> l >> r;
cout << dp[l][r];

偽代碼

FOR k <- 1 to N
    FOR i <- 1 to N
       FOR j <- 1 to N
           dis(i, j) <- min(dis(i, k) + dis(k, j), dis(i, j))

Time Complexity:

$O(N^3)$

為甚麼迴圈的順序是 k, i, j 呢？

看看以下的圖：

假設迴圈擺放是 i, j, k，那麼 dp[i][j] 只會遍歷「連續的 k 次」

而不管是第

$3,4,5$ 點都無法鬆弛 dp[1][2] (因為 dp[1][2] 是最先被鬆弛的)

這樣就會導致 dp[1][2] 有問題。

因此想法應該是對每個點窮舉所有 dp[i][j] 鬆弛。

優點：經過一次 Floyd-Warshall 後，所有兩點最短距離就都知道了！

Bellman-Ford 演算法

由 Floyd-Warshall 程式碼可知它是對整個圖中的每一點鬆弛。

但我們可以先得知起始點，並對「邊」進行鬆弛。

$\Rightarrow$ 一次只能跑出一個點對所有點的最短路徑，dp[i] 代表一點 u 走到 i 點的最短距離

由於一條最短路最多會經過

$n-1$ 條邊，因此只要對每個邊鬆弛

$n-1$ 次就好。

因此又誕生一個演算法：Bellman-Ford

struct road{
	int l, r, val;
};
int main(){
	int n, e, l, r, v;
	cin >> n >> e;
	vector<int> dp(n + 1, 1e9);
	vector<road> rd(e << 1);
	for(int i = 0; i < e; i++){
		cin >> l >> r >> v;
		rd[i << 1] = {l, r, v};
		rd[i << 1 | 1] = {r, l, v};
	}
	cin >> l >> r;
	dp[l] = 0;
	for(int i = 0; i < n - 1; i++){
		for(int j = 0; j < e * 2; j++){
			dp[rd[j].r] = min(dp[rd[j].r], dp[rd[j].l] + rd[j].val);
		}
	}
	for(auto & i : dp) cout << i << ' '; // l 到每個點的距離
	return 0;
}

偽代碼

STRUCT edge{
   point from, to 
   value val
}
//dis(k) <- the distance from st to k
dis(st) <- 0
dis(else) <- INF

//from -> to

FOR i <- 1 to N //repeat N times
    FOR e <- all_edge 
        dis(e.to) <- min(dis(e.to), dis(e.from) + e.val)

而觀察以下圖：

從第

$2$ 點到第

$3$ 點的最短路徑是

$2$ 還是

$-1$ 還是

$-4$ …呢？

由於這種圖(負環)沒有最短路徑，需排除。

而負環會鬆弛超過

$N-1$ 次，因此可以在 Bellman-Ford 演算法結束後判斷。

for(int j = 0; j < e * 2; j++){
	if(dp[rd[j].r] > dp[rd[j].l] + rd[j].val) cout << "neg cycle\n";
}

Time Complexity:

$O(NE)$

演算法：成熟期

這時，有比較快的演算法出現。

SPFA (Shortest Path Faster Algorithm)

從 Bellman-Ford 可得知，它是對每個邊都鬆弛。

然而，在求兩點距離時，一個點被鬆弛過，才可以去鬆弛其他點。

而可鬆弛的點會從原點開始擴散。

這時實作及概念會有點像 BFS。

就是從起點 i 擴散，到達每一點 k 時一樣要判斷 dis[k] = min(dis[j] + dis(j, k), dis[k])

而因為它是 Bellman-Ford 演算法的優化版，因此它也可以檢查負環。

#define mem(x) memset(x, 0, sizeof(x))
struct road{
	int r, val;
};
int main(){
	int n, e, l, r, v;
	cin >> n >> e;
	vector<int> dp(n + 1, 1e9);
	vector<road> rd[n + 1];
	for(int i = 0; i < e; i++){
		cin >> l >> r >> v;
		rd[l].push_back({r, v});
		rd[r].push_back({l, v});
	}
	cin >> l >> r;
	dp[l] = 0;
	queue<int> que;
	que.push(l);
	bool check[n + 1]; mem(check);
	int cnt[n + 1]; mem(cnt);
	while(!que.empty()){
		int tmp = que.front(); que.pop();
		check[tmp] = 0, cnt[tmp]++;
		if(cnt[tmp] >= n) {cout << "neg cycle\n"; break;}
		for(auto & i : rd[tmp]){
			if(dp[i.r] > dp[tmp] + i.val){
				dp[i.r] = dp[tmp] + i.val;
				if(!check[i.r]) check[i.r] = 1, que.push(i.r);
			}
		}
	}
	for(auto & i : dp) cout << i << ' ';
	return 0;
}

幾個實作上的新東西：

1. check[] 判斷點不在 queue 內才可以做 BFS (不然用 queue 裡的點做 BFS 就好)
2. cnt[] 判斷點被丟進 queue 幾次，用來檢查負環
3. struct road 剩下 r, val，因為 l 可以用 vector 的下標搞定
4. 一個點被鬆弛過，才可以去鬆弛其他點

Time Complexity:

$O(NE)$ 但有很大的常數優化 (剪枝)

---

最後，還有一個幾乎是最優的演算法。

但它無法檢查負環，也不能解有負環的題目。

不過…要檢查負環的題目數量趨近於

$0$

Dijkstra 演算法

想法：從起點延伸出去的邊中，先把所有邊都丟進一個容器裡(權重設定為 dis(start, i) + v)，

再選出容器中權重最小的邊，把它接起來，此時權重即為連接到的 j 點權重。

接著以 j 為原點擴散，把連接到的邊丟進容器，重複動作直到連接至終點。

為了讓容器有「選出最小邊」的功能，因此選用 priority_queue

#define mem(x) memset(x, 0, sizeof(x))
struct road {
	int r, val;
	bool operator<(road rd) const {return val >= rd.val;} //pick the smallest
};
int main() {
	int n, e, l, r, v;
	cin >> n >> e;
	vector<int> dis(n + 1, 1e9);
	vector<road> rd[n + 1];
	bool visited[n + 1]; mem(visited);
	for(int i = 0; i < e; i++){
		cin >> l >> r >> v;
		rd[l].push_back({r, v});
		rd[r].push_back({l, v});
	}
	priority_queue<road> pq;
	cin >> l >> r;
	int tmp = l;
	dis[l] = 0; visited[l] = 1;
	while(tmp != r){
		for(auto & i : rd[tmp]) {
			if(!visited[i.r])
				pq.push({i.r, dis[tmp] + i.val});
		}
		road tp_rd;
		while(visited[tmp]){
			tp_rd = pq.top(), pq.pop();
			tmp = tp_rd.r;
		}
		visited[tmp] = 1, dis[tmp] = tp_rd.val;
	}
	for(auto & i : dis) cout << i << ' ';
	return 0;
}

dis(st) <- 0
dis(else) <- INF

min_dis() // get the min_dis val and position
min_dis() add (0, st)

WHILE min_dis() != empty 
    now_pos <- min_dis()    
    del min_dis()
    
    IF is_vis(now_pos) 
        continue
    
    dis(now_pos) <- now_pos.val
    //vis = true
    
    FOR e <- edge(now_pos) // the edges that is from now_pos
        IF not_vis(e.to) :
            min_dis() add (now_pos.val + e.val, e.to)

Time Complexity:

$O(NlgE)$

題目練習：DanDanJudge

a577. 避難所

這題是「兩點最短路」的變化題，因為可能不只一個避難所。

可以把所有避難所的 dis[i] 都先設為

$0$，

而因為沒有負環，所以用 dijkstra 就好。

code

#include<bits/stdc++.h>
#define mem(x) memset(x, 0, sizeof(x))
#define LL long long
using namespace std;
struct road {
	LL r, val;
	bool operator<(road rd) const {return val >= rd.val;} //pick the smallest
};
int main() {
	cin.tie(nullptr), ios_base::sync_with_stdio(false);
	int n, m, k, r, lt, rt, v;
	cin >> n >> m >> k >> r;
	vector<LL> dis(n + 1, 1LL * 1e15);
	vector<road> rd[n + 1];
	bool visited[n + 1]; mem(visited);
	for(int i = 0, root; i < k; i++) 
		cin >> root, dis[root] = 0, visited[root] = 1;
	for(int i = 0; i < m; i++){
		cin >> lt >> rt >> v;
		rd[lt].push_back({rt, v});
		rd[rt].push_back({lt, v});
	}
	int visit = n - k - r, tmp;
	priority_queue<road> pq;
	for(int i = 1; i <= n; i++){
		if(visited[i]){
			tmp = i;
			for(auto & j : rd[i]){
				if(!visited[j.r])
					pq.push({j.r, j.val});
			} 
		}
	}
	
	while(visit--){
		for(auto & i : rd[tmp]) {
			if(!visited[i.r])
				pq.push({i.r, dis[tmp] + i.val});
		}
		road tmp_rd;
		while(visited[tmp]){
			tmp_rd = pq.top(), pq.pop();
			tmp = tmp_rd.r;
		}
		visited[tmp] = 1, dis[tmp] = tmp_rd.val;
	}
	cout << dis[tmp] << '\n';
	return 0;
}

技術及經驗總結

其實…記 dijkstra 就好，因為其他真的太少用到了

有餘力再去記其他演算法