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

①唐巧玲?、卩崟悦?/p>

一、緒論

最短路徑問(wèn)題因?yàn)槠鋯?wèn)題的普遍性，以及應(yīng)用的實(shí)際性，不僅是數(shù)據(jù)結(jié)構(gòu)的熱點(diǎn)問(wèn)題，也是數(shù)學(xué)信息學(xué)科、計(jì)算機(jī)學(xué)科、地理信息學(xué)科等學(xué)科的一個(gè)研究熱點(diǎn)。由于科學(xué)技術(shù)的不斷進(jìn)步，使得應(yīng)用數(shù)學(xué)中的圖論與計(jì)算機(jī)算法與結(jié)構(gòu)結(jié)合，出現(xiàn)了不一樣的較短路徑算法。最短路徑即點(diǎn)到點(diǎn)之間的路徑是最短的，因此可以看作計(jì)算機(jī)中的圖片問(wèn)題，即如何從圖片上找到兩個(gè)頂點(diǎn)的路徑所經(jīng)過(guò)的最短路徑，而最短路徑算法也就提供了如何尋找某兩點(diǎn)之間最短距離的思路。

二、最短路徑算法介紹

最短路徑是圖論與復(fù)雜網(wǎng)絡(luò)分析中的一個(gè)經(jīng)典問(wèn)題。最短路徑算法則是將所需要求的問(wèn)題，轉(zhuǎn)化為圖論問(wèn)題，并通過(guò)相關(guān)的操作，最終得到問(wèn)題所求的最短路徑的過(guò)程。本文采用一個(gè)由n個(gè)節(jié)點(diǎn)和m條邊組成的圖G（V，E）作為路徑圖，V集合存放G中所有的頂點(diǎn)，E集合存放G中所有的邊，將頂點(diǎn)之間存在的邊的權(quán)值設(shè)為w。

（一）最短路徑的基本概念

最短路徑問(wèn)題是求由源點(diǎn)到達(dá)圖中其他任一頂點(diǎn)的最短路徑，即在由節(jié)點(diǎn)構(gòu)成的路徑圖中，找出一條經(jīng)過(guò)路徑的權(quán)值總和最短的路徑。在圖論研究中，假設(shè)將設(shè)置為源點(diǎn)，終點(diǎn)設(shè)為V_j，則尋找最短路徑的形式有以下幾種：

1、源點(diǎn)確定，求最短路徑。

2、終點(diǎn)確定，求最短路徑則需要進(jìn)行討論分析;若在無(wú)向圖中，終點(diǎn)確定可以轉(zhuǎn)化為頂點(diǎn)確定的問(wèn)題來(lái)進(jìn)行解決;若在有向圖中，就需要將路徑方向反轉(zhuǎn)，通過(guò)找起點(diǎn)來(lái)確定此時(shí)終點(diǎn)確定下來(lái)的最短路徑。

3、源點(diǎn)終點(diǎn)都確定，直接進(jìn)行尋找兩點(diǎn)之間的最短路徑。

4、全局最短路徑，可以運(yùn)用以上三種方法，求出任意兩點(diǎn)之間的最短路徑。

（二）Diikstra算法

Diikstra算法運(yùn)用貪心策略的思想。首先，每次找到離源點(diǎn)最近的一個(gè)頂點(diǎn)，記錄源點(diǎn)到此頂點(diǎn)的距離，并標(biāo)記此頂點(diǎn)，接著查找未標(biāo)記頂點(diǎn)到源點(diǎn)的距離，與通過(guò)標(biāo)記點(diǎn)經(jīng)過(guò)的距離進(jìn)行比較，最終找到源點(diǎn)與其他各個(gè)頂點(diǎn)之間的最短路徑。

Diikstra算法的具體步驟如下：

1、將圖中所有頂點(diǎn)分為兩類，分別存放在P和Q兩個(gè)集合中。其中P集合存放的頂點(diǎn)是已經(jīng)求出了與源點(diǎn)存在最短路徑的頂點(diǎn);Q集合存放的是未被求出與源點(diǎn)存在最短路徑的頂點(diǎn)，同時(shí)設(shè)置源點(diǎn)到自身之間的距離為0，源點(diǎn)與其他頂點(diǎn)之間存在直接邊，則設(shè)置源點(diǎn)到此頂點(diǎn)直接距離為該邊權(quán)值V，而把源點(diǎn)與頂點(diǎn)之間不存在直達(dá)邊的距離設(shè)置為∞;

2、已知源點(diǎn)到自身的距離為0是默認(rèn)的，故直接將源點(diǎn)放入P中;

3、在Q集合尋找距離源點(diǎn)最近的頂點(diǎn)V_i，并將頂點(diǎn)V_i放入P中，表示以求得源點(diǎn)到頂點(diǎn)V_i之間的最短路徑;

4、重復(fù)第3步，將Q集合中的點(diǎn)遍歷完畢，算法結(jié)束，源點(diǎn)到圖中所有頂點(diǎn)之間的最短路徑也查找完畢。

（三）Floyd算法

三、最短路徑算法研究

本文使用了Dijkstra算法和Floyd算法，針對(duì)具體問(wèn)題建立模型，并通過(guò)兩種算法的不同算法結(jié)果來(lái)進(jìn)行分析比較。

（一）問(wèn)題分析

某公司在六個(gè)城市有分公司，記為ci，則從ci到cj的直接航程票價(jià)如表3.1.1所示（∞表示無(wú)直接航路），要求找到一個(gè)城市到其他城市間票價(jià)最便宜的路線圖。

表1 某公司總航線表

根據(jù)表1得到某公司總航線圖如圖1所示，其中權(quán)值代表ci到cj的直接航程票價(jià)。因此上述問(wèn)題就可轉(zhuǎn)換成圖論研究中的最短路徑問(wèn)題。因?yàn)槠瘘c(diǎn)和終點(diǎn)都不確定，則需對(duì)全局最短路徑進(jìn)行求解。

圖1 某公司總航線圖

（二）模型的建立和求解

通過(guò)問(wèn)題分析，本文基于MATLAB平臺(tái)，使用Dijkstra算法和Floyd算法對(duì)上述全局最短路徑問(wèn)題進(jìn)行求解，從而得到一個(gè)城市到另一個(gè)城市之間的最便宜票價(jià)。

1、Dijkstra算法

假設(shè)以第一個(gè)城市c1為源點(diǎn)，求源點(diǎn)c1到除源點(diǎn)外的頂點(diǎn)的最短路徑，首先用矩陣存放各邊權(quán)值的鄰接矩陣，行向量pb、index₁、index₂、d分別用來(lái)存放標(biāo)號(hào)信息、標(biāo)號(hào)順序、標(biāo)號(hào)頂點(diǎn)索引、最短通路的值。

根據(jù)上述設(shè)置和數(shù)據(jù)求第一個(gè)城市到其他城市的最短路徑的核心代碼如下：

while sum（pb）

m=find（pb==0）：

d（m）=min（d（m），d（temp）+a（temp，m））：

tmpb=find（d（m）==min（d（m）））：

temp=m（tmpb（1））：

pb（temp）=1;

indexl=[index1，temp];

index=index1（find（d（index1）==d（temp）-a（temp，index1）））：

if length（index）>=2

index=index（1）：

end

index2（temp）=index：

end

由此，可得出運(yùn)用Dijkstra算法求解出的c1至其他城市的最短路徑如圖所示。

圖2 Dijkstra算法實(shí)例cl源點(diǎn)最短路徑圖

2、Floyd算法

首先初始化數(shù)據(jù)，設(shè)置無(wú)窮大值M=100000，矩陣f存放表3.1.1的數(shù)據(jù)值，一個(gè)與矩陣f同等大小的全零矩陣path，用于存放任意兩個(gè)頂點(diǎn)最短路徑的中間節(jié)點(diǎn)k。

求任意兩城市之間的最短路徑的核心代碼如下：

四、仿真及結(jié)果對(duì)比分析

（一）結(jié)果分析

通過(guò)matlab仿真平臺(tái)，以c1為源點(diǎn)，使用Uijkstra算法和Floyd算法可以得到如圖3和圖4的結(jié)果，從圖中可知Dijkstra算法得到的是單原點(diǎn)到其他頂點(diǎn)的數(shù)據(jù)，而Floyd算法最后得出的path表格可以查詢?nèi)我鈨牲c(diǎn)之間的節(jié)點(diǎn)，從而得到任意兩點(diǎn)間的最短路徑。

圖3 Dijkstra算法最短路徑圖

圖4 Floyd算法path圖

相對(duì)于Diikstra算法，F(xiàn)loyd算法更加全面與簡(jiǎn)潔，效率比n次的Dijkstra算法要高，因此Floyd算法更適用于多源最短路徑，可以算出任意兩個(gè)頂點(diǎn)之間的最短距離。

（二）兩種算法比較

首先從算法思想的角度出發(fā)，Dijkstra算法是在尋找最短路徑時(shí)進(jìn)行串行的尋找模式，雖然做到了局部最優(yōu)，但不能實(shí)現(xiàn)整體最短，除此之外Diikstra算法的代碼冗長(zhǎng)繁瑣，效率較低;而Floyd算法較簡(jiǎn)潔，效率高。

在執(zhí)行上，Diikstra算法會(huì)進(jìn)行兩次遍歷，一是先將所有與源點(diǎn)相連的點(diǎn)作為中間點(diǎn)遍歷;二是在中間點(diǎn)的基礎(chǔ)上對(duì)相鄰且未標(biāo)記的點(diǎn)進(jìn)行遍歷。所以Dijkstra算法的時(shí)間復(fù)雜度和空間復(fù)雜度都是O（n*n）;Floyd算法則經(jīng)過(guò)了第一次對(duì)中間點(diǎn)k遍歷，第二次對(duì)源點(diǎn)i遍歷，最后對(duì)終點(diǎn)j的三次遍歷，時(shí)間復(fù)雜度是O（n*n*n）。因此Floyd算法時(shí)間復(fù)雜度高，不適合計(jì)算大量數(shù)據(jù)。

五、結(jié)論

本文完整描述了Dijkstra和Floyd兩種最短路徑算法的算法思想和實(shí)現(xiàn)步驟，并針對(duì)同一實(shí)際問(wèn)題使用matlab平臺(tái)對(duì)這兩種算法進(jìn)行了仿真。通過(guò)對(duì)仿真結(jié)果的對(duì)比分析可得，F(xiàn)loyd算法相較于Diikstra算法實(shí)現(xiàn)更簡(jiǎn)單，效率更高，因此解決此類問(wèn)題會(huì)更偏向于Floyd算法，但其時(shí)間復(fù)雜度也更高，不適于計(jì)算大量數(shù)據(jù)的模型。諸如此類的最短距離問(wèn)題不僅僅適用于本文的例子，還可以運(yùn)用到其他很多地方。但本文提出的方法對(duì)解決此類問(wèn)題只有一定的參考作用，在實(shí)際問(wèn)題中需要依據(jù)不同的情況和要求，對(duì)算法進(jìn)行正確的選擇和適當(dāng)?shù)恼{(diào)整。