迪克斯屈拉最短路徑算法圖論論-wenkub
2023-01-22 03:16:58 本頁(yè)面
【正文】 ，依據(jù)算法的思想，分別實(shí)現(xiàn)了 Dijkstra 算法在求解計(jì)算網(wǎng)絡(luò)最短路徑的應(yīng)用程序。姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 1 計(jì)算機(jī)網(wǎng)絡(luò)中迪克斯屈拉 最短路徑 算法 的程序?qū)崿F(xiàn)及應(yīng)用 沈敬紅 S140131109 重慶郵電大學(xué)通信與信息工程學(xué)院 摘要： 本文首先介紹了圖論的發(fā)展歷程，介紹了圖論在實(shí)際問(wèn)題中的應(yīng)用。 關(guān)鍵詞： 最短路徑 服務(wù)器 Dijkstra 算法 程序 Abstract in this paper, we firstly introduce the process of theory of graph. secondly, we give the introduction of the problem of shortest path and related content, and the application of works which a lot of severs have to search the shortest path. And then shows the one of shortest path algorithms: The Dijkstra algorithm. Finally, according to the ideas of this algorithm, we put forward a method to achieve the procedure using in the works. Key word Shortest— paths Sever Dijkstra Program 引 言 圖論 (Graph Theory)是數(shù)學(xué)的一個(gè)分支。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉 1736 年的論著中，他所考慮的原始問(wèn)題有很強(qiáng)的實(shí)際背景。同樣，比如需要架設(shè)電網(wǎng)、通信網(wǎng)絡(luò)以及其他的有線(xiàn)網(wǎng)絡(luò)，基于全網(wǎng)的考慮之下，點(diǎn)和點(diǎn)之間怎樣架設(shè)一條最短的線(xiàn)路就是一個(gè)實(shí)際的最短路問(wèn)題。 鏈：設(shè) u 和 v 是任意圖 G 的頂點(diǎn)，圖 G 的一條 uv 鏈（ chain 或 walk）是有限的頂點(diǎn)和邊交替的序列 u0e1u1e2… un1enun(u=u0,v=un),其中與邊 e（ 1≤ i≤ n）相鄰的兩個(gè)頂點(diǎn) ui 和 ui1 正好是 ei 的兩個(gè)端點(diǎn)。若邊 e 標(biāo)記數(shù)為 k，則稱(chēng)邊 e 的權(quán) (weight)為 k。 問(wèn)題描述 在現(xiàn)有的 Inter 中存在著大量的不同種類(lèi)的服務(wù)器 [7]，這些服務(wù)器為用戶(hù)提供不同種類(lèi)的數(shù)據(jù)服務(wù)，在服務(wù)器與服務(wù)器之間存在著數(shù)據(jù)的交流。此方法的基本姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 3 思想是：把圖中所有結(jié)點(diǎn)分成兩組，第一組包括已確定最短路徑的頂點(diǎn)，第二組包括尚未確定最短路徑的頂點(diǎn) ，按最短路徑長(zhǎng)度遞增的順序逐個(gè)把第二組的頂點(diǎn)加到第一組中，直到從 V1 出發(fā)可以到達(dá)的所有頂點(diǎn)都已包括在第一組中。 V1對(duì)應(yīng)的距離值為 0，第二組的頂點(diǎn)對(duì)應(yīng)的距離值是這樣確定的：若圖中有弧〈 V1，Vj〉，則 Vj 的距離為此弧的權(quán)值，否則 Vj 的距離為 ∞（或用一個(gè)很大的數(shù)表示）。如此進(jìn)行下去，直到圖中所有頂點(diǎn)都包括在第一 組中 ，或再也沒(méi)有可加入到第一組中的頂點(diǎn)存在為止。 邊的權(quán)值為 adjacent 對(duì)應(yīng)的位置的值 ，數(shù)組元素的下標(biāo)等于相關(guān)聯(lián)頂點(diǎn)序號(hào)。源點(diǎn)為 Vk(其中 k 為 1) （ 3）解決上述問(wèn)題迪克斯屈拉程序源代碼為： include iostream using namespace std。 //鄰接陣，存放邊值 int n。i++) { distance_shortest[i]=adjacent[source][i]。 } s[source
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1