[摘要]最短路徑問題是圖論中的一個重要問題，其應用面相當廣泛。到目前為止，最短路徑算法及其應用已成為一個專業課題。本文將從其源自的數學分支——圖論開始引入，重點介紹最短路徑的兩個重要算法和最短路徑算法在交通道路方面的應用。
　　[關鍵詞]最短路徑，圖論，算法，
　　
　　1.引言
　　最短路徑問題是圖論研究中的一個重要問題，因此它的研究成為不同領域專家學者共同關注的問題。提出許多行之有效的算法。對于各種實際問題的解決提供了數學依據。隨著研究的深入，最短路徑算法也越來越豐富。本文將對最短路徑問題從邏輯聯系上做一下串接，對兩個重要的算法進行系統的介紹。
　　2.最短路徑問題
　　圖論是一種直觀、清晰地表達已知信息的方式。特別是隨著計算機科學的發展，圖論也得到迅速的發展，成為一個十分活躍的數學分支。特別是圖論中的最短路徑問題被廣泛的應用在工程、運輸等方面，尤其在運籌學模型中最短路徑問題已是不可缺少的一種方法。
　　我們可以用頂點代表城市，兩個頂點之間的連線代表在兩個城市之間建造的鐵路。整個鐵路系統構成一個連通圖，任意兩個頂點之間都有一條通路。在連通圖中聯系兩個頂點的邊上標注一個數值，代表這兩個頂點（城市）的實際距離或鐵路造價。這樣就將一個實際問題轉化成了一個最短路徑問題。
　　像這樣的每條邊上都標注了一個數值的圖，我們稱之為帶權圖。一般地設，若相對的每條邊都有一個實數，則稱為邊上的權，并稱為帶權圖。當時（e是連接兩個頂點，的邊），也可將記作，并規定任意的，，當，不相鄰時，。
　　在一個帶權連通圖中，、為任意兩點，從到可能有好幾條路徑，在這些路徑中，從到的帶權總和最小的那條路徑，即為從到的最短路徑。的帶權總和便為從到的距離，記作。
　　最短路徑問題一般包括以下五種情況：1．從某一節點到其它所有節點之間的最短路徑；2．在各對節點之間的最短路徑；3．在兩個規定節點之間的最短路徑；4．從某些規定節點通過某些規定節點之間的最短路徑；5．次短或較短路徑等。
　　第一種情況應用得最為廣泛。要尋找某一節點到其他所有節點之間的最短路徑，實質上是要生成一棵路徑樹。如圖1所示，它正是節點1到其余所有節點的一棵路徑樹，其中樹根即為節點1。某節點V的后繼節點是指從到樹根（r）唯一路徑上的相鄰節點。例如，節點2的后繼節點為節點1，節點7的后繼節點為節點3。顯然樹根沒有后
　　繼節點。
　　
　　圖1路徑樹
　　這樣，此路徑樹則可由一系列后繼節點來確定。圖1所示的樹可由—，1，1，3，4，3，3來定義。它實際上可看成是一個數組，其中第項可用表示，它標示出網絡中第個節點的后繼節點號。如該數組中符號“—”表示節點1（樹根）沒有后繼節點，第2項“1”表示節點2的后繼節點是1號節點，如此等等。另外，從某節點到根節點（）的唯一路徑也能通過一系列后繼節點來跟蹤。如圖1中節點7到根節點1的路徑可從節點7到（節點3），然后到（節點1）。該數組為。最短路徑算法的基本設計思想正是基于上述原理，即從所有其它節點到節點的路徑將形成一棵樹；樹中從某個節點到根節點的唯一路徑即為節點和之間的最短路徑。
　　3.最短路徑問題兩個重要算法
　　最短路徑問題是一種“最優解”問題，其算法多種多樣。其中著名的有Dijkstra算法和Ford-Fulkerson算法。此外還有螞蟻算法、Warshall算法、動態規劃算法。這些算法本文本文不做具體介紹。
　　(1)Dijkstra算法
　　求最短路徑的較好算法是由丹麥計算機科學家B.W.Dijkstra于1959年給出的標號法，也稱Dijkstra算法。算法解決的是有向圖中最短路徑問題。舉例來說，如果圖中頂點表示城市，而邊上的權表示城市間的距離。Dijkstra算法可以用來找到兩個城市之間的最短路徑。而且它可為任一源頂點找出與其它所有節點的最短路徑。在尋徑時要分步由源節點開始一步步地向相鄰頂點擴展，直到包含所有網絡節點為止。
　　其方法是：建立一個節點集，開始時只包含源節點，每算一步中增加一個相鄰節點，直到所有網絡節點均進入中后才結束計算。算法步驟如下：
　　1．初始化處理，定義數組，它只包含源節點，，并定義距離，為非源節點中的其它某個節點，該距離為節點到源節點的鏈路長度；若與直接相鄰，則有一確定值。若與不直接相鄰，則。
　　2．不斷求得數組以外的節點，使距離最小，并將節點F加入原來的數組，對于以外的各節點，按下式更新距離：
　　
　　當，則以代入原，否則維持原值不變。這一過程重復至所有節點均包含在數組N為止。
　　該算法的實現流程主要包括：輸入節點鄰接矩陣，輸入源節點號，輸入距離，計算最短距離；修改源節點號，重新輸入距離，重新計算最短距離，重復此過程，直至所有節點均被修改為源節點號為止。
　　Dijkstra算法的主要特點是以起始點為中心向外層擴展，直到擴展到終點為止。算法能得出最短路徑的最優解，但由于它遍歷計算的節點很多，所以效率低。Dijkstra算法還有一個缺點，那就是它對應的圖，如果圖是全連通的，那么這種算法肯定是很好的，如果不是全連通的，最終的值就不一定是最優的。
　　(2)Ford-Fulkerson算法
　　Ford-Fulkerson算法是另一種著名的最短路經算法。這一方法是用一對數給每一個節點進行標志，并逐步修改，最后得到最短路徑。在此算法中，若由某節點向另一節點發送報文，先要發送給它的相鄰節點，若是的相鄰節點集，而是其中的一個節點，則必有：，式中為節點經到的通路長度；為，兩相鄰節點間的距離；為由到的最短路徑長度。
　　若中考慮了每一個節點，并對每一個相鄰節點均按上式計算一遍，然后比較結果，找出其中最短的一個，記為，它即為最短路徑
　　
　　同理可得到到的最短路徑。這樣一直進行到目的節點A。該算法的具體步驟如下：
　　1．初始化處理，對所有節點都給予形式的標號。
　　2．求每個節點與源節點的最短距離，并反復修改節點上的標號為最短距離的標號，尋找支路，使之滿足

 1/2    1 2 下一頁 尾頁