數據結構最短路徑算法及其應用

韓加軍

摘 要： 最短路徑算法研究是計算機科學研究的熱門話題，不僅具有重要的理論意義，而且具有重要的實用價值。最短路徑問題可以引申為最快路徑問題、最低費用問題等，但它們的核心算法都是最短路徑算法。經典的最短路徑算法——Dijkstra和Floyd算法是目前最短路徑問題采用的理論基礎。本文主要對Dijkstra和Floyd算法進行闡述和分析，然后運用這兩個算法解決兩個簡單的實際問題。

關鍵詞： 最短路徑 Dijkstra算法 Floyd算法 圖論

最短路徑，就是在所有路徑中找到一條距離最短的路徑，而我們所說的最短路徑不僅指地理意義的距離最短，而且可以引申到其他度量，如時間、費用、路線容量。相應地，最短路徑問題就成為最快路徑問題，最低費用問題等，所以我們所說的最短路徑也可以看做最優(yōu)路徑問題。最短路徑問題在交通網絡結構的分析，交通運輸路線的選擇，通訊線路的建造與維護，運輸貨流的最小成本分析，城市公共交通網絡的規(guī)劃等方面，都有直接應用的價值。最短路徑問題在實際中常用于汽車導航系統(tǒng)及各種應急系統(tǒng)等這些系統(tǒng)，一般要求計算出到出事地點的最佳路線的時間應該在1s到3s內，在行車過程中還需要實時計算出車輛前方的行駛路線，這就決定了最短路徑問題的實現應該是高效的。經典圖論與不斷發(fā)展完善的計算機數據結構及算法的有效結合使新的最短路徑算法不斷涌現。

一、圖論基本概念

1.圖的定義。圖（graph）是一種較線性表和樹更為復雜的數據結構，圖與線性表和樹的結構區(qū)別表現在結點之間的關系上，線性表中的每個結點（除首尾結點外）都有一個前驅結點和一個后繼結點，結點與結點之間的關系是一對一的關系；樹上的每個結點都有一個父結點（根結點除外）和一個或多個孩子結點（葉子結點除外），結點與結點的關系是一對多的關系；而圖中結點之間的關系是多對多的關系，結點與結點之間的連接是任意的，每對結點間可以有連接也可以沒有連接。

2.圖的存儲結構。除了存儲圖中各個頂點本身的信息外，還要存儲頂點與頂點之間的所有關系。常用的圖的存儲結構有鄰接矩陣、鄰接表、十字鄰接表和鄰接多重表。

二、最短路徑問題

所謂最短路徑即從圖G中某對頂點Vi和Vj（i≠j）之間的所有路徑中選出權值之和最短的一條路徑作為頂點Vi到頂點Vj的最短路徑。其中邊的權值可多種，如路途、費用、耗時等，也可以同時存在多種權值，根據給定的比例，算出邊的綜合權值。

1.最短路徑。在一個無權的圖中，若從一個頂點到另一個頂點存在一條路徑，則稱該路徑長度為該路徑上經過的邊的數目，等于該路徑上的頂點數減1。由于從一個頂點到另一個頂點可能存在多條路徑，每條路徑上經過的邊數不同，即長度不同，把長度最短的那條叫做最短路徑。

2.最短路徑算法。求圖中最短路徑有兩方面問題：求圖中某一頂點到其余各頂點的最短路徑與求圖中每一對頂點之間的最短路徑。它們分別有Dijkstra算法和Floyd算法。

2.1Dijkstra算法。Dijkstra算法又稱為標號法，是用于求解單源點最短路徑的實用算法，至今仍然被公認為是解決從固定點出發(fā)到網絡中的任意頂點的最短路徑問題的較好方法之一。基本思想如下：設置并逐步擴充一個集合S，存放已求出其最短路徑的頂點，則尚未確定最短路徑的頂點集合是V-S，其中，V為網中所有頂點集合。按最短路徑長度遞增的順序逐個用V-S中的頂點加到S中，直到S中包含全部頂點，而V-S為空。

2.2Floyd算法。Floyd算法能夠求得任意頂點之間的最短路徑?；舅枷胧侨我?個頂點vi到vj的距離的帶權鄰接矩陣開始，每次插入一個頂點vk，然后將vi到vj間的已知最短路徑與插入頂點vk作為中間頂點時可能產生的vi到vj路徑距離比較，取較小值以得到新的距離矩陣。如此循環(huán)迭代下去，依次構造出N個矩陣D（1），D（2）…D（n），當所有頂點均作為任意 2個頂點vi到vj中間頂點時得到的最后的帶權鄰接矩陣D（n）就反映了所有頂點對之間的最短距離信息，成為圖G的距離矩陣。

三、 應用舉例

1.Dijkstra算法在公交網絡中的應用。在紛繁復雜的城市公交網中，如果想尋找到一條從當前某個站點到達另一個目的站點的最短路徑應該怎樣實現呢？針對這個問題采用圖論中最短路徑思想進行了思考和研究，并采用Dijkstra算法實現搜尋計算操作和過程。

（1）實際問題描述。公交網絡中最短路徑問題可以描述為從某起始站點S出發(fā)到達目的站點E，其中S和E之間可行的線路往往不只一條，而是有很多條，那么這么多可行線路中哪一條是最短的呢？這里“最短”指實際走過的路程最短，或指在不計算公交換乘花費時間和公車保持勻速行駛的前提下，能夠以最短時間到達目的地中的“最短”。要求解這個問題如果不考慮其他各方面的復雜因素，就可以看成一個簡單的最短路徑問題。

（2）數學模型建立。起始站點、目的站點及所有可行路徑和中間站點構成的交通網絡，可以抽象為一個圖狀的數據模型——有向帶權圖記為G=（V，E，L），其中V表示所有站點的集合，假設共有N個站點；E表示所有直接通路或直通邊的集合，假設共有M條直通邊，注意，在實際應用中，這里的邊是有方向性的，邊的方向表示該直接通路的可行方向；L表示每條直接通路對應的邊權集合，即每條直通邊對應的距離值或時間開銷等。

（3） 實際問題抽象化。經過上述分析和建模，實際最短路徑問題可抽象為有向帶權圖中兩頂點之間的最短路徑問題。

四、結語

若尋找從起始點到其他所有頂點的最短路徑，按照Dijkstra算法則最多需要經過N-1步的搜尋計算操作（N表示G中的頂點個數）。在實際應用中，Dijkstra算法稱為單源點最短路徑算法。事實上，Dijkstra最短路徑算法除了可以用在公交網絡上之外，還可以用在現實生活的很多方面，如郵政線路、物流線路、管道布線等，我們還可以不斷將其推廣應用于更多方面，從而使數學與計算機科學能夠更充分地為人類服務。

參考文獻：

[1]嚴蔚敏，吳偉民.數據結構[M].北京：清華大學出版社，2002.

[2]李春葆，曾慧，張植民.數據結構程序設計題典[M].北京：清華大學出版社，2002.

[3]張永，李睿，年福忠.算法與數據結構[M].北京：國防工業(yè)出版社，2008.

[4]劉玉龍.數據結構與算法實用教程[M].北京：電子工業(yè)出版社，2007.

[5]徐俊明.圖論及其應用[M].合肥：中國科學技術大學出版社，2004.

[6]曹曉東，原旭.離散數學及算法[M].北京：機械工業(yè)出版社，2007.