> 上次的講義: [Minimum Spanning Tree](/Bp3bb9eYRyyK0TKKbMIHZg)
## 什麼是最短路徑
在圖上，如果我們要從A節點走到B節點，通常不會只有一條路徑
而最短路徑就是**從A到B途中經過的邊權重和最小的路徑**
如下圖所示
從A到B的最短路徑權重總和為 $4$
<!-- 應該要解釋一下負環不存在最短路 -->
---
不過下圖
左上到右下的點最短路是..5?
等等好像不是欸，是...4?
**可以發現若且唯若一張圖存在負環則不存在最短路**
## 如何求最短路徑
要求最短路徑，最直覺的解法就是爆搜
枚舉從A開始的每條邊，直到碰到B為止
再從多條路徑之間找出最小值
i.e.
```cpp=
struct edge{ int b, w; };
vector<vector<edge>> e(n);
vector<bool> visited(n, false);
function<int(int)> dfs = [&] (int cur) {
if (visited[cur]) return 1e9;
if (cur == b) return 0;
int minn = 1e9;
for (auto& i : e[cur])
minn = min(minn, dfs(i.b) + i.w);
return minn;
};
cout << dfs(a) << endl;
```
但在完全圖中，這個演算法的複雜度高達 $O(V!)$
就算我們利用前面學過(?)的技巧來減少可能的分支
i.e.
```cpp=
struct edge{ int b, w; };
vector<vector<edge>> e(n);
vector<bool> visited(n, false);
int minpri = 1e9;
function<void(int, int)> dfs = [&] (int cur, int d) {
if (visited[cur]} || d > minpri) return;
if (cur == b) {minpri = min(minpri, d); return;}
for (auto& i : e[cur])
dfs(i.b, d + i.w);
}; dfs(a, 0);
cout << minpri << endl;
```
還是沒辦法保證複雜度會是好的
勢必需要更快一點的演算法
## 鬆弛 Relaxation
對於兩點之間的距離 dis(a, b)，若存在一點k使得dis(a, k) + dis(k, b) < dis(a, b)，我們就稱這過程為鬆弛
這是解決最短路問題裡很核心的概念
## Floyd-Warshall
有了鬆弛的概念後，就能很容易理解這個最短路演算法了
我們重新看一下鬆弛的式子$$dis[a][b] = min(dis[a][b], dis[a][k] + dis[k][b])$$
因為對於一個點而言，他最多能被其他|V|-1個點鬆弛，所以我們可以假設dp狀態為$$dp(k, i, j)$$
代表從i走到j經由前k個節點鬆弛後的結果，那麼我們就能得出轉移式為$$dp(k + 1, i, j) = min\{dp(k, i, j), dp(k, i, k + 1) + dp(k, k + 1, j)\}$$
```cpp=
int dis[V][V];
for(int k = 0; k < V; ++k)
for(int i = 0; i < V; ++i)
for(int j = 0; j < V; ++j)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
```
Time Complexity: $O(|V|^3)$
## Bellman-Ford
由於一條最短路的長度不會超過|V|-1，所以我們可以重複|V|-1次對所有邊進行鬆弛
此演算法也可以用來檢查負環，因為一條最短路最多被鬆弛|V|-1次，若且唯若能被鬆弛|V|次則存在負環
```cpp=
struct Edge{
int u, v, w;
};
int V, E;
vector<Edge> edge(E);
void Bellman_Ford(int sourse) {
int dis[V];
for(int i = 0; i < V; ++i) dis[i] = inf; // initialize
dis[sourse] = 0; // 原點設為0
// Relaxation
for(int i = 0; i < V - 1; ++i)
for(int j = 0; j < E; ++j)
if(dis[edge[j].u] + edge[j].w < dis[edge[j].v])
dis[edge[j].v] = dis[edge[j].u] + edge[j].w;
// 檢查負環
for(int i = 0; i < E; ++i)
if(dis[edge[i].u] + edge[i].w < dis[edge[i].v])
cout << "A!";
}
```
Time Complexity: $O(|V||E|)$
## SPFA (Shortest Path Faster Algorithm)
SPFA基本上是Bellman-Ford的優化版
可以發現Bellman-Ford都是很無腦的嘗試鬆弛每個點，不過我們知道對於一個點而言，只有在他被鬆弛後，這個點才有可能鬆弛其他點。
因此，SPFA多維護了一個佇列來挑選可能作為鬆弛的點，直到佇列為空就代表鬆弛結束。
```cpp=
#define MEM(x) memset(x, 0, sizeof(x)); // NICE OUO
const int INF = 1e9;
vector<pair<int, int>> edge[V]; // edge[u] = {{v0, w0}, ...}
void SPFA(int src) {
int dis[V], cnt[V]; bool inqueue[V];
MEM(cnt); MEM(inqueue);
fill(dis, dis + V, INF); dis[src] = 0;
queue<int> que; que.push(src); inqueue[src] = 1;
while(!que.empty()) {
int u = que.top(); que.pop();
inqueue[u] = 0;
if(++cnt[u] >= V) { // check negcycle
cerr << "GG there's a neg cycle XD";
break;
}
for(auto [v, w] : edge[u]) if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
if(!inqueue[v]) inqueue[v] = 1, que.push(v);
}
}
}
```
Average Time Complexity: $O(|E|)$
Worst-Case Time Complexity: $O(|V||E|)$
**雖然期望複雜度是$O(|E|)$，但很容易構造出$O(|V||E|)$的測資，所以還是要把他當$O(|V||E|)$來用**
## Dijkstra
上次上課有學過[Prim](/Bp3bb9eYRyyK0TKKbMIHZg#Prim’s-algorithm)
而Dijkstra的概念和實作都和Prim幾乎一模一樣
差別只在
* **Prim是以到MST的距離做鬆弛**
* **Dijkstra是以到起始點的距離作鬆弛**
```cpp=
struct edge {
int b, w;
friend bool operator<(edge a, edge b) {
return a.w > b.w;
}
};
vector<vector<edge>> e(n);
vector<int> d(n, 1e9);
vector<bool> visited(n, false);
priority_queue<edge> pq;
pq.emplace(a, d[a] = 0);
for (int i = 0; i != n; i++) {
int a = ~0u;
while (pq.size() && visited[a = pq.top()]) pq.pop();
if(!~a) break;
else visited[a] = true;
for (const auto& i : e[cur])
if (d[a] + i.w < d[i.b])
pq.emplace(i.b, d[i.b] = d[a] + i.w);
}
```
---
~~我想複習一下dijkstra 所以再多寫一個講解XD~~
~~沒我好累~~
Sign in with Wallet
Connect another wallet