# DS Shortest Path

{%hackmd theme-dark %}

## 最短路

### 鬆弛

若一個點到 a 的最短距離比到 b 的最短距離大超過 x，可以先走 b 再走到 a 來更新 a 的距離

也就是找到一條路徑後看看有沒有其他條路徑比他短

### Dijkstra algorithm

是一種單點源最短路徑演算法

以貪心策略來走 -> 每次都選權重最小的路走

每次都會找一個離新的點最近的點，並以他為起點對其他邊鬆弛

* 不適合用於負權邊

### Floyd-Warshall algorithm

多源最短路徑演算法

可處理負權邊，但不可解負權環

把每個點都當起點後找到所有最短路徑，會對整張圖鬆弛

複雜度為 O(V^3)

模板：

for(int k = 1; k <= N; ++k){
	for(int i = 1; i <= N; ++i){
		for(int j = 1; j <= N; ++j){
			edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j])
		}
	}
}

### Bellman Ford algorithm

鬆弛模式跟 Dijkstra 一樣，但 Dijkstra 只會鬆弛一次，而 Bellman Ford 每次都鬆弛

缺點是複雜度高達 O(VE)