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

①唐巧玲　②鄭曉敏

一、緒論

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

二、最短路徑算法介紹

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

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

最短路徑問題是求由源點到達圖中其他任一頂點的最短路徑，即在由節點構成的路徑圖中，找出一條經過路徑的權值總和最短的路徑。在圖論研究中，假設將設置為源點，終點設為V_j，則尋找最短路徑的形式有以下幾種：

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

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

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

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

（二）Diikstra算法

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

Diikstra算法的具體步驟如下：

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

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

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

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

（三）Floyd算法

三、最短路徑算法研究

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

（一）問題分析

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

表1 某公司總航線表

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

圖1 某公司總航線圖

（二）模型的建立和求解

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

1、Dijkstra算法

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

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

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算法

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

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

四、仿真及結果對比分析

（一）結果分析

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

圖3 Dijkstra算法最短路徑圖

圖4 Floyd算法path圖

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

（二）兩種算法比較

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

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

五、結論

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