最短路問題

最短路問題是圖論理論的一個經典問題。尋找最短路徑就是在指定網絡中兩結點間找一條距離最小的路。最短路不僅僅指一般地理意義上的距離最短,還可以引申到其它的度量,如時間、費用、線路容量等。

最短路徑算法的選擇與實現是通道路線設計的基礎,最短路徑算法是計算機科學與地理信息科學等領域的研究熱點,很多網絡相關問題均可納入最短路徑問題的範疇之中。經典的圖論與不斷髮展完善的計算機數據結構及算法的有效結合使得新的最短路徑算法不斷湧現。

對最短路問題的研究早在上個世紀60年代以前就卓有成效了,其中對賦權圖的有效算法是由荷蘭著名計算機專家E.W.Dijkstra在1959年首次提出的,該算法能夠解決兩指定點間的最短路,也可以求解圖G中一特定點到其它各頂點的最短路。後來海斯在Dijkstra算法的基礎之上提出了海斯算法。但這兩種算法都不能解決含有負權的圖的最短路問題。因此由Ford提出了Ford算法,它能有效地解決含有負權的最短路問題。 ^{[2]  [1]} 

包括確定起點的最短路徑問題，確定終點的最短路徑問題（與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。） 。

求解單源最短路徑問題可以採用Dijkstra算法，時間複雜度為O(|V|^2)。Dijkstra算法可以使用斐波那契堆、配對堆等支持Decrease-Key操作的數據結構來進一步優化，優化後的時間複雜度為O(|E|+|V|log|V|)。 ^[2] 

Dijkstra只可求無負權的最短路徑，因為其目光短淺，看不到後面可以消減的量。在正數中容易得證，若aB的距離固定為1，不再改變，但其實A->B最短路是-1，雖然A->C的最短路是正確的，為-2，但這樣的算法是不可使用的。

如果圖1中有負權迴路，可以採用Bellman-Ford算法，算法複雜度是O(|V||E|)。但Bellman-ford算法浪費了許多時間做無必要的鬆弛，可用SPFA算法進行優化，SPFA算法是用隊列進行的優化，優化後時間複雜度為O(k|E|)， 其中k為所有頂點進隊的平均次數，可以證明k一般小於等於2，由此可見該優化的效果十分顯著。 ^[1] 

求圖1中所有的最短路徑可以採用Floyd-Warshall算法，算法時間複雜度為O(|V|^3)。對於稀疏圖，還可採用Johnson算法，其採用Bellman-ford和Dijkstra作為其子函數，時間複雜度為O（VElgV）。二者都可計算含負權路徑的圖，但不可含有負環。 ^[1] 

即已知起點和終點，求兩結點之間的最短路徑。通常可以用廣度優先搜索（BFS）、深度優先搜索（DFS）等方式來實現，時間複雜度是O(|V|)。 ^{[1]  [1]} 

運用最短路原理，解決交通運輸管理系統的問題，具有非常重要的現實意義。根據實時交通狀況，賦予城市路網中每段線路以時間權值，利用最短路原理，計算出車輛運行時間最短的路線並彙總，通過新媒體及時向廣大羣眾發佈信息，指導廣大羣眾選擇行駛路線，進一步提高現有道路通行能力，提高道路服務水平，滿足現代化高速發展的需求。 ^[1] 

利用圖論的經典理論和人羣流量理論研究艦船人員通道路線的優化設計及最優線路選擇。對船舶通道進行路網抽象,建立網絡圖,然後根據人羣流動的相關理論,選取不同擁擠情況下的人員移動速度,從而確定各條路段(包括樓梯)的行程時間。以行程時間作為通道網絡的路權，得出路阻矩陣以選擇一對起點/終點的最短時間路線為目標,建立最短路徑問題的數學模型,利用經典的Floyd算法確定最短路徑。將此方法應用於某艦艇多層甲板的通道網絡中,計算結果並進行討論,最後在此研究的基礎上對通道設計相關問題的深化和拓展進行了探討和總結,並提出設想。 ^[1] 

火災救護，物流選址，網絡空間建設等等，有着極為廣泛的應用。 ^[1] 

本文研究了一個雙目標最短路問題的變形問題，在該變形問題中，一個目標函數還是路的長度，另一個目標函數則是路的容量。在Paretooptimal最優解的意義下，本文給出了一個時間複雜性為O(n3)的算法，在字典序最優解的意義下，本文給出了一個時間複雜性為O(n2)的算法。 ^[3] 

對 (BsP )，在Pareto一optimal意義下,有時間複雜性為O(n3)的算法。

下面分析算法的時間複雜性,每循環一次至少刪去一個頂點,每次循環調用兩次Dijkstra算法，故算法的時間複雜性為O (n3)。

對(BsP)，在字典序意義下有時間複雜性為o(n2)的算法。

注：該算法在一定意義下是最好的，因為找一條：

→

的路的時間複雜性都為O(n2)。

矩陣算法是求解不含負迴路的網絡中所有頂點對之間最短路的有效算法之一，但當節點比較多時，計算的矩陣多，重複計算量大，降低了計算效率。為此，提出了一種優化的矩陣算法，該算法的思路是利用權矩陣計算網絡任意兩節點之間的最短路長。計算實例表明，優化的矩陣算法減少了重複計算，簡化了路徑標註方法，提高了計算效率。 ^[4] 

PSO 算法的早期收斂非常快，在算法初期應在保證粒子多樣性的基礎上，儘快讓算法進入局部搜索，才能獲得更好的求解效率；而在算法後期則粒子應保留一定的搜索能力，避免過早收斂。

對不含負迴路的網絡中所有頂點對之間的最短路問題，通常採用Floyd算法。對此算法進行了討論，並對Floyd算法的計算過程作了一點改進。改進後的算法對階數不太大的網絡進行較簡單的計算就能得出所有頂點對之間的最短路。 ^[5] 

可以將問題分解，先找出最短的距離，然後在考慮如何找出對應的行進路線。如何找出最短路徑呢，這裏還是用到動態規劃的知識，對於任何一個城市而言，i到j的最短距離不外乎存在經過i與j之間的k和不經過k兩種可能，所以可以令k=1，2，3，...，n(n是城市的數目)，在檢查d(ij)與d(ik)+d(kj)的值；在此d(ik)與d(kj)分別是目前為止所知道的i到k與k到j的最短距離，因此d(ik)+d(kj)就是i到j經過k的最短距離。所以，若有d(ij)>d(ik)+d(kj)，就表示從i出發經過k再到j的距離要比原來的i到j距離短，自然把i到j的d(ij)重寫為d(ik)+d(kj)，每當一個k查完了，d(ij)就是目前的i到j的最短距離。重複這一過程，最後當查完所有的k時，d(ij)裏面存放的就是i到j之間的最短距離了。