來源：互聯網
最短路問題（short-path problem）：若網絡中的每條邊都有一個數值（長度、成本、時間等），則找出兩節點（通常是源節點和阱節點）之間總權和最小的路徑就是最短路問題。最短路問題是網絡理論解決的典型問題之一，可用來解決管路鋪設、線路安裝、廠區布局和設備更新等實際問題。
單源最短路徑
包括確定起點的最短路徑問題，確定終點的最短路徑問題（與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的確定起點的問題。） 。求解單源最短路徑問題可以采用Dijkstra算法，時間復雜度為O(|V|^2)。Dijkstra算法可以使用斐波那契堆、配對堆等支持Decrease-Key操作的數據結構來進一步優化，優化后的時間復雜度為O(|E|+|V|log|V|)。
全局最短路徑
求圖中所有的最短路徑可以采用Floyd-Warshall算法，算法時間復雜度為O(|V|^3)。如果圖中有負權回路，可以采用Bellman-Ford算法，算法復雜度是O(|V||E|)。但Bellman-ford算法浪費了許多時間做無必要的松弛，可用SPFA算法進行優化，SPFA算法是用隊列進行的優化，優化后時間復雜度為O(k|E|)，其中k為所有頂點進隊的平均次數，可以證明k一般小于等于2，由此可見該優化的效果十分顯著。
兩點最短路徑
即已知起點和終點，求兩結點之間的最短路徑。通常可以用廣度優先搜索（BFS）、深度優先搜索（DFS）等方式來實現，時間復雜度是O(|V|)。
參考資料 >