最短路問題的全局最短路徑求圖中所有的最短路徑可以采用Floyd-Warshall算法，算法時間復雜度為O(|V|^3)。如果圖中有負權回路，可以采用Bellman-Ford算法，算法復雜度是O(|V||E|)。但Bellman-ford算法浪費了許多時間做無必要的松弛，可用SPFA算法進行優化，SPFA算法是用隊列進行的優化，優化后時間復雜度為O(k|E|)，其中k為所有頂點進隊的平均次數，可以證明k一般小于等于2，由此可見該優化的效果十分顯著。{0}2，最短路徑的解決方法用于解決最短路徑問題的算法被...