最短路問題的各種求法（一）
最短路問題分為
- 單源最短路（從一個點到另一個點的最短路）
- 多源匯最短路（起點終點不確定）
圖分為稀疏圖和稠密圖
- 稀疏圖 m與n在一個數量級上
- 稠密圖 m與n^2在一個數量級上
求最短路問題的各種方法
- 單源最短路
當所有邊權都是正數用Dijkstra演算法
Dijkstra演算法
- 樸素版Dijkstra演算法
應用于稠密圖 時間復雜度 O(n^2) 空間復雜度 O(n^2) - 堆優化版的Dijkstra演算法（小根堆）
應用于稀疏圖 時間復雜度 O(mlogn) 空間復雜度 O(mn)
當存在負權邊用Bellman-Ford演算法或者spfa演算法
Bellman-Ford演算法
時間復雜度O(nm) 空間復雜度O(m+n)
PS:有邊數限制的最短路只能用 Bellman-Ford演算法
spfa演算法
spfa演算法是對于Bellman-Ford演算法的優化
時間復雜度一般是O(m) 最壞是O(nm) 空間復雜度O(m+n)
PS:一般來說很多問題都可以用spfa演算法但是它的時間復雜度最壞是O(nm)所以會有被卡的風險
- 多源匯最短路
Floyd演算法
時間復雜度O(n^3) 空間復雜度O(n^2)
這是我最喜歡的演算法了，因為實在是太簡單了三重回圈直接搞定！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/279630.html
標籤：其他
下一篇：堆（Heap）的基本知識和堆排序