實驗二路由協議Dijkstra算法的編程與實現編輯ppt一、實驗目的

介紹Dijkstra算法

Dijkstra算法是典型最短路算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。已知條件是整個網絡拓撲和各鏈路的長度。討論這種算法，即尋找從源結點到網絡中其他各結點的最短路徑。編輯ppt二、實驗原理

令D(v)為源結點(記為結點1)到某個結點v的距離，它就是從結點1沿某一路徑到結點v的所有鏈路的長度之和。再令l(i,j)為結點i至結點j之間的距離。整個算法只有以下兩個部分：

(1)初始化令N表示網絡結點的集合。先令N={1}。對所有不在N中的結點v，寫出

在用計算機進行求解時，可以用一個比任何路徑長度大得多的數值代替∞。對于上述例子，可以使D(v)=99。編輯ppt(2)尋找一個不在N中的結點w，其D(w)值為最小。把w加入到N中。然后對所有不在N中的結點v，用[D(v),D(w)+l(w,v)]中的較小的值去更新原有的D(v)值，即：

D(v)←Min[D(v),D(w)+l(w,v)](3)重復步驟(2)，直到所有的網絡結點都在N中為止。

編輯ppt例如：步驟ND(2)D(3)D(4)D(5)D(6)初始化{1}251∞∞1{1,4}24①2∞2{1,4,5}231②43{1,2,4,5}②31244{1,2,3,4,5}2③1245{1,2,3,4,5,6}2312④編輯ppt

現在我們對以上的最短路徑樹的找出過程進行一些解釋。

因為選擇了結點1為源結點，因此一開始在集合N中只有結點1。結點1只和結點2,3和4直接相連，因此在初始化時，在D(2)，D(3)和D(4)下面就填入結點1到這些結點相應的距離，而在D(5)和D(6)下面填入∞。下面執行步驟1。在結點1以外的結點中，找出一個距結點1最近的結點w，這應當是w=4，因為在D(2)，D(3)和D(4)中，D(4)=1，它的之值最小。于是將結點4加入到結點集合N中。這時，我們在步驟1這一行和D(4)這一列下面寫入①，數字1表示結點4到結點1的距離，數字1的圓圈表示結點4在這個步驟加入到結點集合N中了。接著就要對所有不在集合N中的結點（即結點2,3,5和6）逐個執行（E-1）式。對于結點2，原來的D(2)=2?，F在D(w)+l(w,v)=D(4)+l(4,2)=1+2=3>D(2)。因此結點2到結點1距離不變，仍為2。編輯ppt對于結點3，原來的D(3)=5?，F在D(w)+l(w,v)=D(4)+l(4,3)=1+3=4<D(3)。因此結點3到結點1的距離要更新，從5減小到4。對于結點5，原來的D(5)=∞?，F在D(w)+l(w,v)=D(4)+l(4,5)=1+1=2<D(5)。因此結點5到結點1的距離要更新，從∞減小到2。對于結點6，現在到結點1的距離仍為∞。步驟1的計算到此就結束了下面執行步驟2。在結點1和4以外的結點中，找出一個距結點1最近的結點w?，F在有兩個結點（結點2和5）到結點1的距離一樣，都是2。我們選擇結點5（當然也可以選擇結點2，最后得出的結果還是一樣的）。以后的詳細步驟這里就省略了，讀者可以自行完成剩下的步驟。編輯ppt三、算法實現輸入輸出格式輸入格式:第1行:一個數n，代表有n個節點第2-n+1行:每行n個數，代表圖的鄰接矩陣，沒有邊相連為-1