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

一、緒論

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

二、最短路徑算法介紹

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

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

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

1、源點確定，求最短路徑。

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

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

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

（二）Diikstra算法

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

Diikstra算法的具體步驟如下：

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

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

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

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

（三）Floyd算法

三、最短路徑算法研究

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

（一）問題分析

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

表1 某公司總航線表

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

圖1 某公司總航線圖

（二）模型的建立和求解

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

1、Dijkstra算法

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

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

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

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

圖2 Dijkstra算法實例cl源點最短路徑圖

2、Floyd算法

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

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

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

（一）結(jié)果分析

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

圖3 Dijkstra算法最短路徑圖

圖4 Floyd算法path圖

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

（二）兩種算法比較

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

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

五、結(jié)論

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