[科普中國]-最短路問題

理論概要

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

最短路徑算法的選擇與實現(xiàn)是通道路線設計的基礎,最短路徑算法是計算機科學與地理信息科學等領域的研究熱點,很多網(wǎng)絡相關(guān)問題均可納入最短路徑問題的范疇之中。經(jīng)典的圖論與不斷發(fā)展完善的計算機數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)。

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

理論重點單源最短路徑包括確定起點的最短路徑問題，確定終點的最短路徑問題（與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題。） 。

求解單源最短路徑問題可以采用Dijkstra算法，時間復雜度為O(|V|^2)。Dijkstra算法可以使用斐波那契堆、配對堆等支持Decrease-Key操作的數(shù)據(jù)結(jié)構(gòu)來進一步優(yōu)化，優(yōu)化后的時間復雜度為O(|E|+|V|log|V|)。2

Dijkstra只可求無負權(quán)的最短路徑，因為其目光短淺，看不到后面可以消減的量。在正數(shù)中容易得證，若aB最短路是-1，雖然A->C的最短路是正確的，為-2，但這樣的算法是不可使用的。

如果圖中有負權(quán)回路，可以采用Bellman-Ford算法，算法復雜度是O(|V||E|)。但Bellman-ford算法浪費了許多時間做無必要的松弛，可用SPFA算法進行優(yōu)化，SPFA算法是用隊列進行的優(yōu)化，優(yōu)化后時間復雜度為O(k|E|)， 其中k為所有頂點進隊的平均次數(shù)，可以證明k一般小于等于2，由此可見該優(yōu)化的效果十分顯著。1

全局最短路徑求圖中所有的最短路徑可以采用Floyd-Warshall算法，算法時間復雜度為O(|V|^3)。對于稀疏圖，還可采用Johnson算法，其采用Bellman-ford和Dijkstra作為其子函數(shù)，時間復雜度為O（VElgV）。二者都可計算含負權(quán)路徑的圖，但不可含有負環(huán)。1

兩點最短路徑即已知起點和終點，求兩結(jié)點之間的最短路徑。通?？梢杂脧V度優(yōu)先搜索（BFS）、深度優(yōu)先搜索（DFS）等方式來實現(xiàn)，時間復雜度是O(|V|)。11

應用領域城市網(wǎng)絡運用最短路原理，解決交通運輸管理系統(tǒng)的問題，具有非常重要的現(xiàn)實意義。根據(jù)實時交通狀況，賦予城市路網(wǎng)中每段線路以時間權(quán)值，利用最短路原理，計算出車輛運行時間最短的路線并匯總，通過新媒體及時向廣大群眾發(fā)布信息，指導廣大群眾選擇行駛路線，進一步提高現(xiàn)有道路通行能力，提高道路服務水平，滿足現(xiàn)代化高速發(fā)展的需求。1

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

其他應用火災救護，物流選址，網(wǎng)絡空間建設等等，有著極為廣泛的應用。1

應用算法關(guān)于最短路問題的一個雙目標優(yōu)化問題本文研究了一個雙目標最短路問題的變形問題，在該變形問題中，一個目標函數(shù)還是路的長度，另一個目標函數(shù)則是路的容量。在Paretooptimal最優(yōu)解的意義下，本文給出了一個時間復雜性為O(n3)的算法，在字典序最優(yōu)解的意義下，本文給出了一個時間復雜性為O(n2)的算法。3

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

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

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

注：該算法在一定意義下是最好的，因為找一條：→的路的時間復雜性都為O(n2)。

求解最短路問題的一種優(yōu)化矩陣算法矩陣算法是求解不含負回路的網(wǎng)絡中所有頂點對之間最短路的有效算法之一，但當節(jié)點比較多時，計算的矩陣多，重復計算量大，降低了計算效率。為此，提出了一種優(yōu)化的矩陣算法，該算法的思路是利用權(quán)矩陣計算網(wǎng)絡任意兩節(jié)點之間的最短路長。計算實例表明，優(yōu)化的矩陣算法減少了重復計算，簡化了路徑標注方法，提高了計算效率。4

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

最短路問題的Floyd算法的若干討論對不含負回路的網(wǎng)絡中所有頂點對之間的最短路問題，通常采用Floyd算法。對此算法進行了討論，并對Floyd算法的計算過程作了一點改進。改進后的算法對階數(shù)不太大的網(wǎng)絡進行較簡單的計算就能得出所有頂點對之間的最短路。5

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