![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/langzh-hk-640px-6n-graf.svg.png&w=640&q=50)
最短路問題
維基百科,自由的 encyclopedia
最短路徑問題是圖論研究中的一個經典演算法問題,旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑。演算法具體的形式包括:
- 確定起點的最短路徑問題 - 也叫單源最短路問題,即已知起始結點,求最短路徑的問題。在邊權非負時適合使用Dijkstra演算法,若邊權為負時則適合使用Bellman-ford演算法或者SPFA演算法。
- 確定終點的最短路徑問題 - 與確定起點的問題相反,該問題是已知終結結點,求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同,在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
- 確定起點終點的最短路徑問題 - 即已知起點和終點,求兩結點之間的最短路徑。
- 全域最短路徑問題 - 也叫多源最短路問題,求圖中所有的最短路徑。適合使用Floyd-Warshall演算法。
![]() |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/320px-6n-graf.svg.png)
用於解決最短路徑問題的演算法被稱做「最短路徑演算法」,有時被簡稱作「路徑演算法」。最常用的路徑演算法有:
- Dijkstra演算法
- A*演算法
- Bellman-Ford演算法
- SPFA演算法(Bellman-Ford演算法的改進版本)
- Floyd-Warshall演算法
- Johnson最短路演算法(英語:Johnson's algorithm)
- 雙向搜尋