最短路由選擇算法

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

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

最短路徑樹Dijkstra算法

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

最短路徑樹Floyd算法

從代表任意兩個節(jié)點

考慮一個連通無向圖

在一個所有最短路徑都明確（例如沒有負長度的環(huán)）的連通圖，我們可以使用如下算法構造最短路徑樹：

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

對于所有的非根頂點

用各個頂點和它們的父節(jié)點之間的邊構造最短最短路徑樹。

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

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

路由選擇算法可分為自適應型和非自適應型兩大類。自適應型的特點在于它的路由選擇能在一定程度上隨網(wǎng)路運行狀態(tài)（如流量和拓撲）而改變，可避開出現(xiàn)異態(tài)的節(jié)點或鏈路。非自適應型采用靜態(tài)路由選擇算法。常見的非自適應型有擴散式、隨機式、固定式等；而自適應型有集中式、孤立式、分布式等。

固定式是一種應用范圍比較廣的非自適應型路由選擇算法。它是根據(jù)網(wǎng)路拓撲和信息流量的統(tǒng)計模型事先確定各節(jié)點的路由表，每個節(jié)點的路由表指明從該節(jié)點出發(fā)到某個目的節(jié)點所應該選擇的輸出鏈路以及下一節(jié)點。路由表由算法確定，而在固定式中是事先預定的。

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

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

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

算法描述如下：

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

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