最短路問題

維基百科,自由的百科全書
前往: 導覽搜尋
一個有6個節點和7條邊的圖

最短路徑問題是圖論研究中的一個經典演算法問題, 旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑。 演算法具體的形式包括:

  • 確定起點的最短路徑問題 - 即已知起始結點,求最短路徑的問題。適合使用Dijkstra演算法
  • 確定終點的最短路徑問題 - 與確定起點的問題相反,該問題是已知終結結點,求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同,在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
  • 確定起點終點的最短路徑問題 - 即已知起點和終點,求兩結點之間的最短路徑。
  • 全局最短路徑問題 - 求圖中所有的最短路徑。適合使用Floyd-Warshall演算法

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」, 有時被簡稱作「路徑演算法」。 最常用的路徑演算法有: