迪克斯屈拉最短路徑算法圖論論-文庫(kù)吧
2024-12-23 03:16 本頁(yè)面
【正文】 的頂點(diǎn)和邊交替的序列 u0e1u1e2… un1enun(u=u0,v=un),其中與邊 e（ 1≤ i≤ n）相鄰的兩個(gè)頂點(diǎn) ui 和 ui1 正好是 ei 的兩個(gè)端點(diǎn)。 路：內(nèi)部點(diǎn)不同的鏈稱為路（ path） 。 圈：兩端點(diǎn)相同的路（即閉路）稱為圈或回路。 加權(quán)圖：邊上有數(shù)的圖稱為加權(quán)圖（ weighted graph） 。若邊 e 標(biāo)記數(shù)為 k，則稱邊 e 的權(quán) (weight)為 k。在加權(quán)圖中，鏈（跡、路）的長(zhǎng)度為鏈（跡、路）上的所有邊的權(quán)值之和 . 鄰接矩陣：設(shè) G＝ V,E是任意圖，規(guī)定 n 階方陣 A=（ aij）為 G 的鄰接矩陣，其中 aij 為圖 G 中以 xi 為起點(diǎn)且以 yj 為終點(diǎn)的邊的數(shù)目。 邊權(quán)矩陣：設(shè) G＝ V,E是 n 階加權(quán)簡(jiǎn)單圖，規(guī)定 D=（ dij） m n 是圖的加權(quán)矩陣，即 dij＝ w（ i， j）。若結(jié)點(diǎn) i 到結(jié)點(diǎn) j 無(wú)邊可連（在有向圖中是方向不一致）時(shí)，取 dij＝∞。 問(wèn)題描述 在現(xiàn)有的 Inter 中存在著大量的不同種類的服務(wù)器 [7]，這些服務(wù)器為用戶提供不同種類的數(shù)據(jù)服務(wù)，在服務(wù)器與服務(wù)器之間存在著數(shù)據(jù)的交流。如果，我們將各個(gè)服務(wù)器看做是一個(gè)頂點(diǎn)，將服務(wù)器與服務(wù)器之間的鏈接看做是一條邊，則服務(wù)器組成的網(wǎng)絡(luò)就是一個(gè)無(wú)向連通圖 [9]。在這個(gè)圖上，服務(wù)器與服務(wù)器之間的鏈路上都存在著一定的時(shí)延，由于網(wǎng)絡(luò)環(huán)境的不同，每個(gè)邊上的時(shí)延均不相同，有的 只有幾十毫秒，有的卻達(dá)到上百毫秒，這些毫秒數(shù)就可以看做邊的權(quán)值，如何選擇最佳的路徑使得服務(wù)器與服務(wù)器之間的數(shù)據(jù)交換所需時(shí)間最短的問(wèn)題，就變成了求解在無(wú)向連通加權(quán)圖中尋求最短路徑的問(wèn)題。如下圖為網(wǎng)絡(luò)服務(wù)器之間的拓?fù)鋱D： （注： S1S6 為網(wǎng)絡(luò)服務(wù)器節(jié)點(diǎn)，權(quán)值為 10ms/每單位值） 迪克斯屈拉（ Dijkstra）算法實(shí)現(xiàn) Dijkstra 算法 [1]描述： 算法基本思想 ： 一個(gè)頂點(diǎn) V1 作為源點(diǎn)，求該頂點(diǎn)到其他各頂點(diǎn)的最短路徑，迪克斯屈拉 提出了一個(gè)按路徑長(zhǎng)度遞增的順序產(chǎn)生最短路徑的方法。此方法的基本姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 3 思想是：把圖中所有結(jié)點(diǎn)分成兩組，第一組包括已確定最短路徑的頂點(diǎn)，第二組包括尚未確定最短路徑的頂點(diǎn) ，按最短路徑長(zhǎng)度遞增的順序逐個(gè)把第二組的頂點(diǎn)加到第一組中，直到從 V1 出發(fā)可以到達(dá)的所有頂點(diǎn)都已包括在第一組中。在這過(guò)程中，總保持從 V1 到第一組各頂點(diǎn)的最短路徑都不大于從 V1 到第二組的任何頂點(diǎn)的最短路徑長(zhǎng)度。另外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離值，第一組的頂點(diǎn)對(duì)應(yīng)的距離值就是從 V1到此頂點(diǎn)的最短路徑長(zhǎng)度，第二組的頂點(diǎn)對(duì)應(yīng)的距離值是從 V1 到此頂點(diǎn)的只包括第一組的頂點(diǎn)為中間頂點(diǎn)的最短路徑長(zhǎng)度 [2]。 實(shí)現(xiàn)過(guò)程描述 ：一開(kāi)始 第一組 只包括頂點(diǎn) V1，第二組包括其他所有頂點(diǎn)。 V1對(duì)應(yīng)的距離值為 0，第二組的頂點(diǎn)對(duì)應(yīng)的距離值是這樣確定的：若圖中有弧〈 V1，Vj〉，則 Vj 的距離為此弧的權(quán)值，否則 Vj 的距離為 ∞（或用一個(gè)很大的數(shù)表示）。然后每次從第二組的頂點(diǎn)中選一個(gè)其距離值為最小 Vm 的加入到第一組中，每往第一組中加入一個(gè)頂點(diǎn) Vm，就要對(duì)第二組中的各個(gè)頂點(diǎn)的距離值進(jìn)行一次修正。若加進(jìn)Vm 做中間結(jié)點(diǎn)，使從 V1 到 Vj 的最短路徑比不加 Vm 的路徑要短，則要修改 Vj 的距離值。修改后再選距離值最小的頂點(diǎn)加入到第一組中。如此進(jìn)行下去，直到圖中所有頂點(diǎn)都包括在第一 組中 ，或再也沒(méi)有可加入到第一組中的頂點(diǎn)存在為止。 Dijkstra 算法對(duì)問(wèn)題描述及實(shí)現(xiàn)： 六個(gè)服務(wù)器節(jié)點(diǎn) S S S S S5 和 S6，分別如圖表示，各個(gè)端點(diǎn)之間的權(quán)值標(biāo)于節(jié)點(diǎn)間的聯(lián)線之上。 . G=(V,E) （ 1）此有加權(quán)圖的鄰接矩陣表示為： （
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1