or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
Shortest Path最短路徑
3/6
什麼是最短路徑?
通常會有一張圖,要你算從起點\(s\)走到終點\(t\)所需的最小時間or花費
像是4走到5的時間/花費是4

或是2走到3的時間/花費是7
圖也有分有向圖和無向圖

或是有負環或是沒負環

在最短路徑這個演算法上我們要對應不同的圖
使用合適的演算法
存圖技巧
鄰接矩陣
5 <-> 6 花費為 9
matrix[5][6] = matrix[6][5] = 9
鄰接矩陣–存圖
鄰接串列
1 -> 3 權重為 5
表示為 1 : {3, 5}
鄰接串列–存圖
最短路徑分類
單源最短路徑
給你一個圖,一個起點,求出這個起點到每個點的最短路徑

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

演算法們
Dijkstra
想法
由於是單源最短路徑,所以會先創一個陣列,這裡叫dis
一開始會把dis[起點]設為0,代表起點到自己的距離是0
然後把dis[其他點]設為INF,再重複做下面的步驟
什麼是鬆弛
假設 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
學會鬆弛之後我們就可以看看Dijkstra在做什麼了
假設一開始起點是2,要算下圖的最短距離
初始化
先把dis初始化,把起點設為0,其他設為INF(很大的數字)
選一個離起點最近並且沒有走過的點u
\(\to\)選2
把點u設定為走過
\(\to\)visited[2]=1
1
透過所有連接點u和v的邊,去鬆弛點v
1
INF1
INF7
1
選一個離起點最近並且沒有走過的點u
\(\to\)選4
1
把點u設定為走過
\(\to\)visited[4]=1
1
1
透過所有連接點u和v的邊,去鬆弛點v
INF5
1
INF2
1
INF5
1
1
選一個離起點最近並且沒有走過的點u
\(\to\)選3
1
1
把點u設定為走過
\(\to\)visited[3]=1
1
1
1
透過所有連接點u和v的邊,去鬆弛點v
1
1
1
54
1
1
1
選一個離起點最近並且沒有走過的點u
\(\to\)選5
1
1
1
把點u設定為走過
\(\to\)visited[5]=1
1
1
1
1
透過所有連接點u和v的邊,去鬆弛點v
1
1
1
1
1
1
1
1
選一個離起點最近並且沒有走過的點u
\(\to\)選1
1
1
1
1
把點u設定為走過
\(\to\)visited[1]=1
1
1
1
1
1
透過所有連接點u和v的邊,去鬆弛點v
1
1
1
1
1
選一個離起點最近並且沒有走過的點u
\(\to\)選6
1
1
1
1
1
把點u設定為走過
\(\to\)visited[1]=1
1
1
1
1
1
1
透過所有連接點u和v的邊,去鬆弛點v
1
1
1
1
1
1
這樣就走完ㄌ
1
1
1
1
1
1
分析一下可能的複雜度,以下假設\(V\)為點個數,\(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
看看有哪些步驟的複雜度是可以被優化掉的
總複雜度:\(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\))
很明顯這樣複雜度就好了
總複雜度
總複雜度:\(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最小的
範例code:
0-1BFS
小限制
如果圖中有負權邊,Dijkstra這個演算法不能用
因為Dijkstra會取dis最小的點,在有負權邊的情況下會爛掉
起點為1的時候會爛掉

最短路徑樹
當你給定了一個起點,從這個起點走到任意的點的路徑會形成一棵樹(也有可能是多顆)

以下面的例子來說,最短路徑樹有兩顆
下課時間
Bellman-Ford
想法
Bellman-Ford是以每一條邊去做鬆弛,能鬆弛就直接去做鬆弛,直到不能鬆弛為止。

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

以每一條邊去做鬆弛
複雜度:總共\(m\)條邊,鬆弛\(n-1\)次 \(\to O(nm)\)
負環
可以無限減少花費的一個環 (\(1 \to 3 \to 2 \to 1\))

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

判斷負環
若是第\(n\)輪鬆弛還有點被鬆弛到 代表這張圖存在負環
SPFA
其實是Bellman-Ford的優化版本
想法
可以發現Bellman-Ford有很多鬆弛操作是多餘的
只有上一次被鬆弛的節點,所連接的邊,才有可能引起下一次鬆弛
code
我們用一個queue來維護 [可能會引起鬆弛操作的節點]
複雜度
在大部分時候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\)])
實現
空間複雜度:\(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
題目連結