基于MATLAB的最短路徑算法分析

周志進

(貴陽學院 貴州貴陽 550005)

最短路徑算法就是用于計算一個節點到其他節點的最短路徑問題，一般是指確定起點的最短路徑問題，求起始節點到某一終點的最短路徑問題，也常用于已知起點和終點，求解兩節點之間的最短路徑。

1 MATLAB程序概述

MATLAB 是由美國MathWorks 公司出品的數學軟件，MATLAB 意為矩陣工程，將用于一維、二維與三維數值積分的函數進行了統一，并經過基本數學和內插函數的輔助，提供數值分析、矩陣計算等諸多功能，為應用數學、工程設計和數值計算提供全方位的解決方案，很大程度上擺脫了傳統程序設計語言的編輯模式。其高效的數值及符號計算功能，可以幫助用戶快速處理繁雜的數學運算問題，具備的圖形處理功能可以實現計算結果和編程的可視化。MATLAB本身是一個高級的矩陣語言，包括諸多算法、控制語句、函數等面向基本對象或問題的應用程序[1]。比如：在最短路徑計算中可以利用矩陣運算和線性方程組的求解或是數據的統計分析來優化相關問題。

2 基于MATLAB的4種最短路徑算法

2.1 Dijkstra算法

Dijkstra（迪杰斯特拉）算法是最經典的單源最短路徑算法，也就是用于計算一個節點到其他所有節點最短路徑的算法。Dijkstra算法采用貪心算法策略，每次遍歷與起點距離最近且未訪問過的節點，直至擴展到終點。該算法類似于Prim（普里穆）算法在單個節點源中搜索最小生成樹，不過Dijkstra算法要求圖中不存在負權邊[2]。首先假設一個輔助數組，即一個帶權的有向圖G，數組中起始點v到某一節點的最短路徑在算法執行過程中便會算法，但需要注意的是，這個值在計算過程中是不斷逼近最終結果的，并不確定就等于最短路徑距離。按照最短路徑長度的遞增次序，依次向節點中加入未確定最短路徑的頂點s，不斷尋找下一條長度最短的路徑，也就是v至s的最短路徑，當v到s中各頂點的最短路徑長度小于等于v到其余已確定最短路徑的節點時，便可認為s到v的距離就是最短路徑長度，而且v到頂點s，只包括s中頂點為中間點的最短路徑[3]。

2.2 Floyd算法

基于MATLAB 的Floyd-Warshall 算法（簡稱Floyd算法）也是一種著名的解決任意兩點間最短路徑的算法，Floyd算法是利用插點的方式在給定的加權圖上計算多源點的最短路徑算法，從本質上講Floyd算法是一個動態規劃算法。在動態規劃算法中，最為關鍵也是核心理念的就是對于狀態的定義，這是因為Floyd算法的單個執行將找到所有頂點之間的最短路徑長度，并通過對算法的簡單修改來重建路徑，以此驗證加權圖中所有頂點之間的最短路徑。以d[k][i][j]可以定位為例，在使用1至k號節點時，計算點i到點j之間的最短路徑長度。在加權圖中有n個點，從1 到n。k則變為動態規劃算法的松弛操作，也就是描述從起點v到s的最短路徑上權值的上界，也被稱作最短路徑估計，通過d[1][i][j]表示只使用1 點作為中間媒介，點i到點j的最短路徑長度，以此定義狀態，便可構建動態轉移方程。動態轉移就是在加權圖上d[k][i][j]由1 至n轉移到1 至k的一種狀態轉移表示，對這個狀態進行動態轉移，且有兩種情況，i到j最短路徑不經過k；i到j最短路徑經過k。可以得出基于Floyd算法的動態轉移方程：

式中，d[n][i][j]為加權圖中所有頂點之間的最短路徑長度；k、n皆為頂點；而且要注意Floyd算法雖然是一種可以在具有正負邊緣權重加權圖中找到最短路徑的算法，但是并沒有負周期，這就表示動態轉移方程應當在不使用任何點的情況下，滿足兩點之間最短路徑的長度的邊界條件。這樣就可以得出Floyd算法代碼：

動態規劃算法中都具有利用滾動數組的方式減少算法的空間復雜度，以便更快速地求得最優解，常見的Floyd 算法也都是采用二維數組表示狀態。動態轉移方程在隱藏階段索引后就變為：

證明了在第k-1階段和第k階段，點i和點k之間的最短路徑長度是不變的，也可以說明在第k階段到第k-1階段計算中，點k和點j之間的最短路徑長度不變。上一階段的值可以放心用于計算第k階段時d[i][j]的值。

2.3 Bellman-Ford算法

Bellman-Ford算法相比較上述兩種算法可以計算存在負權邊的情況，進行n-1 次更新來找到所有節點的最短路徑長度。雖然Bellman-Ford 算法與Dijkstra算法有些類似，都可以確定一個節點的最短路徑。但不同的是，Bellman-Ford 算法并不知道具體哪個階段的最短路徑確定了，只能知道比上次計算多確定一個，這樣進行n-1 次更新后才能確定所有節點的最短路徑。算法原理是從已知節點連到其余節點的所有邊中的最小邊在更新后就是其余節點的最短距離，進而知道一個可確定的最短距離節點，無所謂它具體是哪個節點。Bellman-Ford 算法的優勢在于可以用來判斷是否存在負環，在不存在負環情況下，進行n-1次更新后便能確定每個節點的最短距離，再用所有邊更新一次依然不會改變結果。但如果存在負環，更新一次會改變結果，造成這種情況的原因就是之前假設起點的最短距離是確定的且最短的，而在負環情況下，這個假設不再成立。Bellman-Ford算法的代碼表示為：

從代碼實現的復雜性就可以看出Bellman-Ford算法的效率并不高。當前如果沒有存在負環基本不會采用此算法，而且下述的SPFA算法也是對Bellman-Ford算法的一種優化。

2.4 SPFA算法

SPFA算法主要應用于給定的加權圖存在負權邊，這種情況下無法運用Dijkstra 算法和Floyd 算法，而Bellman-Ford 算法的復雜度過高。因此，SPFA 算法成為可選的方式。首先，需要約定加權圖基本存在負權邊也不能存在負權回路，保證最短路徑一定存在。雖然可以在執行該算法前做一次拓撲排序，來判斷該加權圖是否存在負權回路，但這與算法的關系不大，因此不深入分析[4]。SPFA算法的本質是動態逼近法，通過假設一個節點隊列來不斷更新隊列中的首尾節點，在首位節點進入隊列后進行松弛操作，如果該節點指向最短路徑距離則進行調整，若指向的節點不在隊列中，則將該節點加入隊列，其中最短路徑在隊列計算中為估計值，隨著隊列的不斷更迭進行調整從而不斷逼近最短距離長度，如此循環直至隊列中不存在節點，便能夠得到節點之間的最短路徑長度。而SPFA算法無法處理帶有負權回路的圖的原因，就是在某個節點進入隊列的次數超過n次，導致隊列一直無法計算出經過該節點的最短路徑。SPFA算法是Bellman-Ford算法的一種隊列實現表示，減少了不必要的冗余計算，原理就是利用隊列中的點與所有與其相鄰的點進行松弛，不斷進行反復迭代來確定最短路徑。SPFA算法的代碼表示為：

SFPA算法有兩個優化算法，為SLF策略和LLL策略，SLF 策略設要加入的節點是j，隊首節點為i，若dist(i)＞dist(j)，則將j插入隊首，否則插入隊尾。簡單明了，可使算法計算速度提高10%。而LLL策略設隊首節點為i，隊列中所有dist 值的平均值為x，若dist(i)＞x則將i插入隊尾，查找下一元素，直到某dist(i)≤x，則對i進行松弛操作。SLF+LLL 可大幅提高SFPA 算法的效率。不過在實際應用中，SFPA 算法的時間效率并不穩定，若出現計算時間很長的情況，可采用更為穩定的Dijkstra算法來計算最短路徑長度[5]。

3 基于MATLAB的最短路徑算法的應用研究

在實際生活中各類基站的分布需要經過實地勘探、測量與分析才能繪制出基本的圖形和方案，根據不同基站節點位置與傳輸距離，篩選出較短的間距。比如換熱站、通信基站等，適宜的間距可以最大程度減少資源傳輸的浪費問題。根據實際基站模型簡化，再將應用圖論簡化為實際基站分布，便可將基站簡化為數個節點，確定一個起始點后，通過基于MATLAB的最短路徑算法來規劃出基站分布的最短間距，并利用MATLAB 程序繪制出基站分布圖，全面表示基站節點之間的距離。特別是很多基站位于城市之中，需要從多條支路方案中篩選出距離相對更近的路線，便可以通過基于MATLAB的Dijkstra算法確定最短路徑，有效降低基站建設和運營成本，從根本上解決運作保障和傳輸距離之間的協調問題[6]。

4 結語

通過分析基于MATLAB的最短路徑算法，可以得到基于MATLAB的不同路徑算法在最短路徑長度計算中的基本原理和代碼實現情況，并通過最短路徑算法的實際應用，了解到最短路徑算法有著良好運用效果，有助于解決各種最優距離、最短距離問題，具有較高的實用性。