最短路由選擇算法

計(jì)算圖中兩個(gè)節(jié)點(diǎn)之間的最短距離有多種算法，其中最著名的算法是Dijkstra在1959年提出的Dijkstra算法 。該算法要求每個(gè)節(jié)點(diǎn)用從源節(jié)點(diǎn)沿已知最佳路徑到本節(jié)點(diǎn)的距離來(lái)標(biāo)注。開(kāi)始時(shí)由于一條路徑也不知道，故所有的節(jié)點(diǎn)都標(biāo)注無(wú)窮大。隨著算法的進(jìn)行和不斷找到的路徑，標(biāo)注隨之改變，使之反映出較好的路徑。一個(gè)標(biāo)注可以是暫時(shí)性的(可更改的)，所有標(biāo)注最初都是暫時(shí)的，但一旦發(fā)現(xiàn)了標(biāo)注代表了從源節(jié)點(diǎn)到該節(jié)點(diǎn)的最短可能路徑時(shí)，就使之成為永久性的，不再進(jìn)行修改。

為了說(shuō)明加標(biāo)注算法是怎樣工作的，請(qǐng)參考右圖，其中數(shù)字表示兩節(jié)點(diǎn)的距離。要找A至D的最短距離，首先A標(biāo)注為永久性的(用實(shí)心圓點(diǎn)表示)作為開(kāi)始，然后依次考察與A相鄰的每個(gè)節(jié)點(diǎn)，用他們各自到A的距離重新標(biāo)注這些點(diǎn)。找到B節(jié)點(diǎn)為最短路徑節(jié)點(diǎn)后使其成為永久節(jié)點(diǎn)，接下來(lái)從節(jié)點(diǎn)B開(kāi)始，檢查所有與B相鄰的節(jié)點(diǎn)，如果B的標(biāo)注與從B到所有節(jié)點(diǎn)距離之和小于此節(jié)點(diǎn)的標(biāo)注，就重新標(biāo)注這個(gè)節(jié)點(diǎn)。 2100433B

最短路徑樹(shù)Dijkstra算法

設(shè)置兩個(gè)定點(diǎn)的集合T和S，集合S中存放已找到最短路徑的定點(diǎn)，集合T中存放當(dāng)前還未找到的最短路徑的定點(diǎn)。初始狀態(tài)時(shí)，集合S中只包含源點(diǎn)v0然后不斷從集合T中選取到定點(diǎn)v0路徑長(zhǎng)度最短的頂點(diǎn)u加入集合S，集合S中每加入一個(gè)新的頂點(diǎn)u，都要修改定點(diǎn)v0到集合T中剩余頂點(diǎn)的最短路徑長(zhǎng)度值，集合T中每個(gè)頂點(diǎn)新的最短路徑長(zhǎng)度值為原來(lái)的最短路徑長(zhǎng)度值與定點(diǎn)u的最短路徑長(zhǎng)度值加上u到該頂點(diǎn)的路徑長(zhǎng)度值中的較小值。此過(guò)程不斷重復(fù)，直到集合T的頂點(diǎn)全部加入到集合S為止 。

最短路徑樹(shù)Floyd算法

從代表任意兩個(gè)節(jié)點(diǎn)

考慮一個(gè)連通無(wú)向圖

在一個(gè)所有最短路徑都明確（例如沒(méi)有負(fù)長(zhǎng)度的環(huán)）的連通圖，我們可以使用如下算法構(gòu)造最短路徑樹(shù)：

使用Dijkstra算法或Floyd算法計(jì)算圖 G 從根節(jié)點(diǎn) v 到 頂點(diǎn) u 的最短距離

對(duì)于所有的非根頂點(diǎn)

用各個(gè)頂點(diǎn)和它們的父節(jié)點(diǎn)之間的邊構(gòu)造最短最短路徑樹(shù)。

上面的算法保證了最短路徑樹(shù)的存在。像最小生成樹(shù)一樣，最短路徑樹(shù)通常也不只有一個(gè)的。在所有邊的權(quán)重都相同的時(shí)候，最短路徑樹(shù)和廣度優(yōu)先搜索樹(shù)一致。在存在負(fù)長(zhǎng)度的環(huán)時(shí)，從

路由選擇方法的精確描述，屬于網(wǎng)路軟件的一部分。對(duì)它的要求是正確、簡(jiǎn)單、可靠、穩(wěn)定、公平和優(yōu)化。

路由選擇算法可分為自適應(yīng)型和非自適應(yīng)型兩大類(lèi)。自適應(yīng)型的特點(diǎn)在于它的路由選擇能在一定程度上隨網(wǎng)路運(yùn)行狀態(tài)（如流量和拓?fù)洌┒淖?，可避開(kāi)出現(xiàn)異態(tài)的節(jié)點(diǎn)或鏈路。非自適應(yīng)型采用靜態(tài)路由選擇算法。常見(jiàn)的非自適應(yīng)型有擴(kuò)散式、隨機(jī)式、固定式等；而自適應(yīng)型有集中式、孤立式、分布式等。

固定式是一種應(yīng)用范圍比較廣的非自適應(yīng)型路由選擇算法。它是根據(jù)網(wǎng)路拓?fù)浜托畔⒘髁康慕y(tǒng)計(jì)模型事先確定各節(jié)點(diǎn)的路由表，每個(gè)節(jié)點(diǎn)的路由表指明從該節(jié)點(diǎn)出發(fā)到某個(gè)目的節(jié)點(diǎn)所應(yīng)該選擇的輸出鏈路以及下一節(jié)點(diǎn)。路由表由算法確定，而在固定式中是事先預(yù)定的。

最短路徑算法為最常用的算法，它尋求在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間能沿著長(zhǎng)度最短的路徑來(lái)傳送分組。這里所指的“長(zhǎng)度”賦于特別含義，既可以是實(shí)際距離，也可以是平均時(shí)延或者鏈路費(fèi)用。長(zhǎng)度參數(shù)是路由表的依據(jù)，如果參數(shù)值來(lái)自網(wǎng)路運(yùn)行的當(dāng)前狀態(tài)，路由表變?yōu)閯?dòng)態(tài)生成，這樣的路由選擇算法就屬于自適應(yīng)型。

Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時(shí)標(biāo)號(hào)的方式。注意該算法要求圖中不存在負(fù)權(quán)邊。

首先，引進(jìn)一個(gè)輔助向量D，它的每個(gè)分量D[i]表示當(dāng)前所找到的從始點(diǎn)v到每個(gè)終點(diǎn)vi的的長(zhǎng)度：如D[3]=2表示從始點(diǎn)v到終點(diǎn)3的路徑相對(duì)最小長(zhǎng)度為2。這里強(qiáng)調(diào)相對(duì)就是說(shuō)在算法過(guò)程中D的值是在不斷逼近最終結(jié)果但在過(guò)程中不一定就等于長(zhǎng)度。它的初始狀態(tài)為：若從v到vi有弧，則D為弧上的權(quán)值；否則置D為∞。顯然，長(zhǎng)度為 D[j]=Min{D | vi∈V} 的路徑就是從v出發(fā)的長(zhǎng)度最短的一條。此路徑為(v,vj)。 那么，下一條長(zhǎng)度次短的是哪一條呢？假設(shè)該次短路徑的終點(diǎn)是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長(zhǎng)度或者是從v到vk的弧上的權(quán)值，或者是D[j]和從vj到vk的弧上的權(quán)值之和。 一般情況下，假設(shè)S為已求得的終點(diǎn)的集合，則可證明：下一條最短路徑（設(shè)其終點(diǎn)為X）或者是弧(v,x)，或者是中間只經(jīng)過(guò)S中的頂點(diǎn)而最后到達(dá)頂點(diǎn)X的路徑。因此，下一條長(zhǎng)度次短的的長(zhǎng)度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的權(quán)值，或者是D[k](vk∈S)和弧(vk,vi)上的權(quán)值之和。

算法描述如下：

1）arcs表示弧上的權(quán)值。若不存在，則置arcs為∞。S為已找到從v出發(fā)的的終點(diǎn)的集合，初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點(diǎn)vi可能達(dá)到的度的初值為D=arcs[Locate Vex(G,v),i] vi∈V

2）選擇vj，使得D[j]=Min{D | vi∈V-S} 3）修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長(zhǎng)度。