基于vc的最短路徑dijkstra算法的實(shí)現(xiàn)-wenkub
2022-11-28 21:44:53 本頁(yè)面
【正文】 留了我們已知的所有 d[v]的值已經(jīng)是最短路徑的值頂點(diǎn)，而集合 Q 則保留其他所有點(diǎn)。如果這個(gè)值比目前已知的 d[v]的值要是小，我們可以用新值來(lái)代替當(dāng)前 d[v]中的值。初始時(shí)，源點(diǎn) s的路徑長(zhǎng)度值被賦予為 0（ d[s]=0） ,同時(shí)把所有其他頂點(diǎn)的路徑長(zhǎng)度設(shè)為無(wú)窮大，即表示我們不知道任何通向這些頂點(diǎn)的路徑（對(duì)于 V 中所有 頂點(diǎn) V 除 S 外的 d[v]= ）。算法解決的是有向圖中最短路徑問(wèn)題。 4) 找到點(diǎn) i 的前一點(diǎn)。③ 標(biāo)記起 源點(diǎn) s，記 k=s,其他所有點(diǎn)設(shè)為未標(biāo)記的。 算法簡(jiǎn)介 Dijkstra 算法的基本思路是：假設(shè)每個(gè)點(diǎn)都有一對(duì)標(biāo)號(hào) (dj, pj)，其中 dj 是從起源點(diǎn) s 到點(diǎn) j 的最短路徑的長(zhǎng)度 (從頂點(diǎn)到其本身的最短路徑是零路 (沒(méi)有弧的路 )，其長(zhǎng)度等于零 )； pj 則是從 s 到 j 的最短路徑中 j 點(diǎn)的前一點(diǎn)。而在所有的特征值計(jì)算中，中間中心度算是最難計(jì)算的一個(gè)。 用于解決最短路徑問(wèn)題的算法被稱做“最短路徑算法”， 有時(shí)被簡(jiǎn)稱作“路徑算法”。通過(guò)本次課程設(shè)計(jì)，我們對(duì)上課所學(xué)得知識(shí)進(jìn)行了鞏固，對(duì)最短路徑、 Dijkstra 算法有了更深得理解。 課程設(shè)計(jì)說(shuō)明書 沈 陽(yáng) 大 學(xué) 基于 VC 的最短路徑 Dijkstra 算法的實(shí)現(xiàn) 為了鞏固“ 通信網(wǎng)基礎(chǔ)及應(yīng)用” 課程學(xué)到的相關(guān)知識(shí)，通過(guò)對(duì)本課程所學(xué)知識(shí)的綜合運(yùn)用，使學(xué)生融會(huì)貫通課程中所學(xué)的理論知識(shí)， 初步 掌握通信網(wǎng)絡(luò)的體系結(jié)構(gòu)和擴(kuò)頻通信系統(tǒng) 等相關(guān)知識(shí) ； 加深對(duì)通信網(wǎng)絡(luò)的基本理論、基本知識(shí)和常用技術(shù)的理解 ；提高學(xué)生分析問(wèn)題的能力和實(shí)踐能力，培養(yǎng)科學(xué)研究的獨(dú)立工作能力。 Dijkstra 算法是用來(lái)求解有向圖（無(wú)向圖可看作特殊的有向圖）的最短路徑的經(jīng)典算法，用于計(jì)算靜態(tài)網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。 最常用的路徑算法有 : 1)Dijkstra 算法 2)A*算法 3)SPFA 算法 4)BellmanFord 算法 5)FloydWarshall 算法 6)Johnson 算法 所謂單源最短路徑問(wèn)題是指已知圖 G=（ V， E），我們希望找出從某給定的源起點(diǎn)S 到 V 中的 每個(gè)節(jié)點(diǎn)的最短路徑。結(jié)點(diǎn)的中間中心度是指一個(gè)社會(huì)網(wǎng)絡(luò)中，結(jié)點(diǎn)控制其他節(jié)點(diǎn)的能力，最早是由Freeman 與 1977 年提出的用于衡量個(gè)體社會(huì)地位的參數(shù)。求解從起源點(diǎn) s 到點(diǎn) j 的最短路徑算法的基本過(guò)程如下： 1) 初始化。 2) 檢驗(yàn)從所有已標(biāo)記的點(diǎn) k到其直接連接的未標(biāo)記的點(diǎn) j 的距離，并設(shè)置： dj=min［ dj, dk+lkj］ 式中， lkj 是從點(diǎn) k 到 j 的直接連接距離。從已標(biāo)記的點(diǎn)中找到直接連接到點(diǎn) i 的點(diǎn) j*，作為前一點(diǎn) ,設(shè)置： i=j* 5) 標(biāo)記點(diǎn) i。舉例來(lái)說(shuō)，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示個(gè)城市間開車行經(jīng)的距離。當(dāng)算法結(jié)束時(shí)， d[v]中儲(chǔ)存的便是從 s 到 v 的最短路徑，或者如果路徑不存在的話是無(wú)窮大。拓展邊的操作一直執(zhí)行到所有的 d[v]都代表從 s到 v最短路徑的花費(fèi)。集合 S初始狀態(tài)為空，而后每一步都有一個(gè)頂點(diǎn)從 Q 移動(dòng)到 S。 S：以求出最短路徑的頂點(diǎn)的集合 VS=T：尚未確定最短路徑的頂點(diǎn)集合將 T 中頂點(diǎn)按最短路徑遞增的次序加入到 S 中，先從源點(diǎn) V0 到 S 中個(gè)頂點(diǎn)的最短路徑長(zhǎng)度都不大于從 V0 到 T 中任何頂點(diǎn)的最短路徑長(zhǎng)度。 DWORD hID。 int nopen = 0。 DWORD version。 if(ret != 0){ printf(Error initializing Winsock.\n)。 scanf(%s,hostname)。 if(starting_port PORT_MIN){ printf
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1