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

 1/2    1 2 下一頁(yè) 尾頁(yè)