計(jì)算機(jī)網(wǎng)絡(luò)實(shí)驗(yàn) 實(shí)驗(yàn)二 路由協(xié)議Dijkstra算法的編程與實(shí)現(xiàn)

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

2、出 在用計(jì)算機(jī)進(jìn)行求解時(shí)，可以用一個(gè)比任何路徑長(zhǎng)度大得多的數(shù)值代替。對(duì)于上述例子，可以使D(v) = 99。(2) 尋找一個(gè)不在N中的結(jié)點(diǎn)w，其D(w)值為最小。把w加入到N中。然后對(duì)所有不在N中的結(jié)點(diǎn)v，用D(v), D(w) + l(w, v)中的較小的值去更新原有的D(v)值，即： D(v)MinD(v), D(w) + l(w, v) (3) 重復(fù)步驟(2)，直到所有的網(wǎng)絡(luò)結(jié)點(diǎn)都在N中為止。 例如：步驟ND(2)D(3)D(4)D(5)D(6)初始化125111, 424221, 4, 5231431, 2, 4, 5312441, 2, 3, 4, 5212451, 2, 3, 4,

3、 5, 62312 現(xiàn)在我們對(duì)以上的最短路徑樹的找出過程進(jìn)行一些解釋。 因?yàn)檫x擇了結(jié)點(diǎn)1為源結(jié)點(diǎn)，因此一開始在集合N中只有結(jié)點(diǎn)1。結(jié)點(diǎn)1只和結(jié)點(diǎn)2, 3和4直接相連，因此在初始化時(shí)，在D(2)，D(3)和D(4)下面就填入結(jié)點(diǎn)1到這些結(jié)點(diǎn)相應(yīng)的距離，而在D(5)和D(6)下面填入。 下面執(zhí)行步驟1。在結(jié)點(diǎn)1以外的結(jié)點(diǎn)中，找出一個(gè)距結(jié)點(diǎn)1最近的結(jié)點(diǎn)w，這應(yīng)當(dāng)是w = 4，因?yàn)樵贒(2)，D(3)和D(4)中，D(4) = 1，它的之值最小。于是將結(jié)點(diǎn)4加入到結(jié)點(diǎn)集合N中。這時(shí)，我們?cè)诓襟E1這一行和D(4)這一列下面寫入，數(shù)字1表示結(jié)點(diǎn)4到結(jié)點(diǎn)1的距離，數(shù)字1的圓圈表示結(jié)點(diǎn)4在這個(gè)步驟加入到結(jié)點(diǎn)集

4、合N中了。 接著就要對(duì)所有不在集合N中的結(jié)點(diǎn)（即結(jié)點(diǎn)2, 3, 5和6）逐個(gè)執(zhí)行（E-1）式。 對(duì)于結(jié)點(diǎn)2，原來的D(2) = 2?，F(xiàn)在D(w) + l(w, v) = D(4) + l(4, 2) = 1 + 2 = 3 D(2)。因此結(jié)點(diǎn)2到結(jié)點(diǎn)1距離不變，仍為2。 對(duì)于結(jié)點(diǎn)3，原來的D(3) = 5?，F(xiàn)在D(w) + l(w, v) = D(4) + l(4, 3) = 1 + 3 = 4 D(3)。因此結(jié)點(diǎn)3到結(jié)點(diǎn)1的距離要更新，從5減小到4。 對(duì)于結(jié)點(diǎn)5，原來的D(5) = ?，F(xiàn)在D(w) + l(w, v) = D(4) + l(4, 5) = 1 + 1 = 2 D(5)。因此結(jié)點(diǎn)5到結(jié)點(diǎn)1的距離要更新，從減小到2。 對(duì)于結(jié)點(diǎn)6，現(xiàn)在到結(jié)點(diǎn)1的距離仍為。 步驟1的計(jì)算到此就結(jié)束了 下面執(zhí)行步驟2。在結(jié)點(diǎn)1和4以外的結(jié)點(diǎn)中，找出一個(gè)距結(jié)點(diǎn)1最近的結(jié)點(diǎn)w?，F(xiàn)在有兩個(gè)結(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)輸入輸出格式輸入格式: 第1行:一個(gè)數(shù)n，代表有n個(gè)節(jié)點(diǎn) 第2-n+1行:每行n個(gè)數(shù)，代表圖的鄰接矩陣，沒有邊相連為-1