周志進(jìn)

(貴陽(yáng)學(xué)院 貴州貴陽(yáng) 550005)

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

1 MATLAB程序概述

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

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

2.1 Dijkstra算法

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

2.2 Floyd算法

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

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

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

證明了在第k-1階段和第k階段，點(diǎn)i和點(diǎn)k之間的最短路徑長(zhǎng)度是不變的，也可以說(shuō)明在第k階段到第k-1階段計(jì)算中，點(diǎn)k和點(diǎn)j之間的最短路徑長(zhǎng)度不變。上一階段的值可以放心用于計(jì)算第k階段時(shí)d[i][j]的值。

2.3 Bellman-Ford算法

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

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

2.4 SPFA算法

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

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

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

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

4 結(jié)語(yǔ)

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