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

周志進

(貴陽學院 貴州貴陽 550005)

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

1 MATLAB程序概述

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

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

2.1 Dijkstra算法

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

2.2 Floyd算法

基于MATLAB 的Floyd-Warshall 算法（簡稱Floyd算法）也是一種著名的解決任意兩點間最短路徑的算法，F(xiàn)loyd算法是利用插點的方式在給定的加權(quán)圖上計算多源點的最短路徑算法，從本質(zhì)上講Floyd算法是一個動態(tài)規(guī)劃算法。在動態(tài)規(guī)劃算法中，最為關(guān)鍵也是核心理念的就是對于狀態(tài)的定義，這是因為Floyd算法的單個執(zhí)行將找到所有頂點之間的最短路徑長度，并通過對算法的簡單修改來重建路徑，以此驗證加權(quán)圖中所有頂點之間的最短路徑。以d[k][i][j]可以定位為例，在使用1至k號節(jié)點時，計算點i到點j之間的最短路徑長度。在加權(quán)圖中有n個點，從1 到n。k則變?yōu)閯討B(tài)規(guī)劃算法的松弛操作，也就是描述從起點v到s的最短路徑上權(quán)值的上界，也被稱作最短路徑估計，通過d[1][i][j]表示只使用1 點作為中間媒介，點i到點j的最短路徑長度，以此定義狀態(tài)，便可構(gòu)建動態(tài)轉(zhuǎn)移方程。動態(tài)轉(zhuǎn)移就是在加權(quán)圖上d[k][i][j]由1 至n轉(zhuǎn)移到1 至k的一種狀態(tài)轉(zhuǎn)移表示，對這個狀態(tài)進行動態(tài)轉(zhuǎn)移，且有兩種情況，i到j(luò)最短路徑不經(jīng)過k；i到j(luò)最短路徑經(jīng)過k?？梢缘贸龌贔loyd算法的動態(tài)轉(zhuǎn)移方程：

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

動態(tài)規(guī)劃算法中都具有利用滾動數(shù)組的方式減少算法的空間復雜度，以便更快速地求得最優(yōu)解，常見的Floyd 算法也都是采用二維數(shù)組表示狀態(tài)。動態(tài)轉(zhuǎn)移方程在隱藏階段索引后就變?yōu)椋?/p>

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

2.3 Bellman-Ford算法

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

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

2.4 SPFA算法

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

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

3 基于MATLAB的最短路徑算法的應(yīng)用研究

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

4 結(jié)語

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