《計算機(jī)網(wǎng)絡(luò)教學(xué)資料》實(shí)驗二

1、實(shí)驗二路由協(xié)議D i j kst r a算法的編程 j 與實(shí)現(xiàn)一、實(shí)驗?zāi)康慕榻BDi jkstra算法Dijkstra算法是典型最短路算法，用于計算一個節(jié)點(diǎn) 到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心 向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。已知條件是整個網(wǎng) 絡(luò)拓?fù)浜透麈溌返拈L度。討論這種算法，即尋找從源結(jié)點(diǎn) 到網(wǎng)絡(luò)中其他各結(jié)點(diǎn)的最短路徑。二、實(shí)驗原理r令(0為源結(jié)點(diǎn)(記為結(jié)點(diǎn)1)到某個結(jié)點(diǎn)啲距離，它 就是從結(jié)點(diǎn)1沿某一路徑到結(jié)點(diǎn)啲所有鏈路的長度之和。 再令1(厶丿)為結(jié)點(diǎn)了至結(jié)點(diǎn)丿之間的距離。整個算法只有 以下兩個部分：(1) 初始化令憔示網(wǎng)絡(luò)結(jié)點(diǎn)的集合。先令二lo對所有不在幷 中的結(jié)點(diǎn)耳寫

2、出f/(l,v)若結(jié)點(diǎn)V與結(jié)點(diǎn)1直接相連(V)= OO若結(jié)點(diǎn)V與結(jié)點(diǎn)1不直接相連在用計算機(jī)進(jìn)行求解時，可以用一個比任何路徑長 度大得多的數(shù)值代替對于上述例子，可以使W)= 99o(2) 尋找一個不在腫的結(jié)點(diǎn)昭 其(分值為最小。把勸口入 到腫。然后對所有不在種的結(jié)點(diǎn)卩，用D3 + 7U 7)的技小的値去更薪原肴的(卩)值，即：Z?(r) *-MinZ?(r), Dw)+ /(%v)(3) 重復(fù)步驟(2),直到所有的網(wǎng)絡(luò)結(jié)點(diǎn)都在腫為止。例如:步驟N0(2)D。(4)0(5)0(6)初始 化125100OO11,4242OO21,4,5231431,2, 4, 53124411,2,3,4,5212

3、451，2, 3, 4, 5, 62312現(xiàn)在我們對以上的最短路徑樹的找出過程進(jìn)行一些解釋。因為選擇了結(jié)點(diǎn)1為源結(jié)點(diǎn)，因此一開始在集合神只 有結(jié)點(diǎn)1。結(jié)點(diǎn)1只和結(jié)點(diǎn)2, 3和4直接相連，因此在初始 化時，在2?(2), (3)和(4)下面就填入結(jié)點(diǎn)1到這些結(jié)點(diǎn) 相應(yīng)的距離，而在(5)和(6)下面填入a。勰黑勸跖鑫欷鑼礬歌器數(shù)字I的下面執(zhí)行步驟1。在結(jié)點(diǎn)1以外的結(jié)點(diǎn)中，找出一個距 結(jié)點(diǎn)1最近的結(jié)點(diǎn)昭這血當(dāng)是二4,囪為在， 和中，Z?(4) = 1,它的之值最小。于是將結(jié)點(diǎn)4加入 刼結(jié)點(diǎn)秦合神。這此 我彳門在步驟1這一行和(4)這一刻和接馨溫會您合神的結(jié)點(diǎn)(即結(jié)點(diǎn)235對于結(jié)點(diǎn)2,原來的(2) =

4、 2o現(xiàn)在(分+ 1(嘰v)= 織處蘇嚴(yán)0(2)。因此結(jié)點(diǎn)2到結(jié)點(diǎn)對于結(jié)點(diǎn)3,原來的(3)二5o現(xiàn)在(內(nèi)+ g v) =(4) + 7(4, 3)二 1 + 3 二 4 (3)。因此結(jié)點(diǎn)3到結(jié) 點(diǎn)1的距離要更新，從5減小到4。對于結(jié)點(diǎn)5,原來的力(5)二o現(xiàn)在0(訥+ 7( v) =(4) + 7(4, 5)二 1 + 1 = 2 (5)。因此結(jié)點(diǎn)5到結(jié) 點(diǎn)1的距離要更新，從8減小到2。對于結(jié)點(diǎn)6,現(xiàn)在到結(jié)點(diǎn)1的距離仍為8。步驟1的計算到此就結(jié)束了下面執(zhí)行步驟2。在結(jié)點(diǎn)1和4以外的結(jié)點(diǎn)中，找出一 個距結(jié)點(diǎn)1最近的結(jié)點(diǎn)現(xiàn)在有兩個結(jié)點(diǎn)(結(jié)點(diǎn)2和5)到 結(jié)點(diǎn)1的距離一樣，都是2。我們選擇結(jié)點(diǎn)5 (當(dāng)然也可以 選擇結(jié)點(diǎn)2,最后得出的結(jié)果還是一樣的)。以后的詳細(xì) 步驟這里就省略了，讀者可以自行完成剩下的步驟。三、算法實(shí)現(xiàn)r輸入輸岀格式輸入格式：第1行:一個數(shù)n,代表有n個節(jié)點(diǎn)第2-n+1行:每行n個數(shù)，代表圖的鄰接矩陣，沒有邊相連另T輸出格