課程設計改_圖文文庫

1、基于dijstra最短路徑算法1課程設計的目的為了鞏固“數(shù)據(jù)通信與通信網(wǎng)技術”課程學到的相關知識，通過對本課程所學知識 的綜合運用，使學生融會貫通課程中所學的理論知識，初步掌握通信網(wǎng)絡的體系結構和 擴頻通信系統(tǒng)等相關知識；加深對通信網(wǎng)絡的基木理論、基木知識和常用技術的理解； 提高學生分析問題的能力和實踐能力，培養(yǎng)科學研究的獨立工作能力。2.設計方案論證問題描述給定一個帶權無向圖g二(v,e),其中每條邊的權是一個非負實數(shù)。另外，還給定v 屮的一個項點，稱為源。現(xiàn)在我們要計算從源到所有其他各項點的最短路徑長度。這里 的長度是指路上各邊權z和，這個問題通常稱為單源最短路徑問題。最短路徑最短路徑問題

2、是圖論研究中的一個經典算法問題，在日常生活中，我們如果需耍 常常往返a地區(qū)和b地區(qū)z間，我們最希望知道的可能是從a地區(qū)到b地區(qū)間的眾多路 徑屮，那一條路徑的路途最短。最短路徑問題是圖論研究屮的一個經典算法問題，旨在 尋找圖(由結點和路徑組成的)屮兩結點z間的最短路徑。算法具體的形式包括：1 確定起點的最短路徑問題-即已知起始結點，求最短路徑的問題。2確定終點的最短路徑問題-與確定起點的問題相反，該問題是已知終結結點， 求最短路徑的問題。在無向圖屮該問題與確定起點的問題完全等同，在有向圖屮該問題 等同于把所有路徑方向反轉的確定起點的問題。3確定起點終點的最短路徑問題-即己知起點和終點，求兩結點之

3、間的最短路 徑。4.全局最短路徑問題-求圖中所有的最短路徑。用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算 法”。算法介紹辿杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉丁 1959年捉出的，因此又叫狄 克斯特拉算法是從一個頂點到其余齊頂點的最短路徑算法，解決的是有向圖中最短路 徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為 止。算法原理1首先，引入一個輔助向量d,它的每個分量d i表示當前所找到的從起始點 v (即源點v)到其它每個頂點vi的長度。例如，d3 = 2表示從起始點到頂點3的路徑相對最小長度為2。這里強調相對就 是說在算法執(zhí)行過程

4、屮d的值是在不斷逼近最終結果但在過程屮不一定就等于長度。2. d的初始狀態(tài)為：若從v到vi有弧(即從v到vi存在連接邊)，則di為弧 上的權值(即為從v到vi的邊的權值)；否則置d 為8。顯然，長度為di=min d|ev 的路徑就是從v出發(fā)到頂點vj的長度最短的一 條路徑，此路徑為(v, vj)o3那么，下一條長度次短的是哪一條呢？也就是找到從源點v到下一個頂點的 最短路徑氏度所對應的頂點，且這條最短路徑長度僅次于從源點v到頂點vj的最短路 徑長度。假設該次短路徑的終點是vk,則可想而知，這條路徑要么是(v, vk),或者是 (v, vj, vk)o它的長度或者是從v到vk的弧上的權值，或者

5、是dj加上從vj到vk 的弧上的權值。4一般情況下，假設s為已求得的從源點v出發(fā)的最短路徑長度的頂點的集合, 則可證明：下一條次最短路徑(設其終點為x)要么是弧(v, x),或者是從源點v出 發(fā)的中間只經過s中的頂點而最后到達頂點x的路徑。因此，下一條長度次短的的最短路徑長度必是d = min d|gv-s , k中di要 么是弧(v, vi)上的權值，或者是dkl(vkes)和弧(vk,vi)上的權值之和。算法思想按路徑長度遞增次序產生算法把頂點集合v分成兩組：（1）s：已求出的頂點的集合（初始時只含有源點v0）（2）v-s=t：尚未確定的頂點集合將t屮頂點按遞增的次序加入到s屮，保證：（1

6、）從源點v0到s中其他各頂點的長度都不大于從v0到t中任何頂點的最短 路徑長度（2）每個頂點對應一個距離值s中頂點：從v0到此頂點的長度t屮頂點：從v0到此頂點的只包括s屮頂點作屮間頂點的最短路徑長度依據(jù)：可以證明v0到t中頂點vk的，或是從v0到vk的直接路徑的權值；或 是從v0經s中頂點到vk的路徑權值z和（反證法可證）求最短路徑步驟算法步驟如下：g二v, e1.初始時令s=vo,t=v-s=其余頂點, t屮頂點對應的距離值若存在 <vo,vi>, d（vo,vi）為vo,vi>弧上的權值若不存在<vo,vi>, d（vo,vi）為82. 從t中選取一個與s中

7、頂點有關聯(lián)邊且權值最小的頂點w,加入到s中3. 對其余t屮頂點的距離值進行修改：若加進w作屮間頂點，從v0到vi的距 離值縮短，則修改此距離值3設計的過程與分析問題算法設g= （v, e）是一個帶權有向圖，把圖中頂點集合v、分成兩組，第一組為已求出最 短路徑的頂點集合（用s表示，初始時s中只有一個源點，以后每求得一條最短路徑，就 將加入到集合s中，直到全部頂點都加入到s中，算法就結束了），第二組為其余未確 定最短路徑的頂點集合（用u表示），按最短路徑長度的遞增次序依次把第二（2）從u中選取一個距離v最小的頂點k,把k,加入s屮（該選定的距離就 是v到k的最短路徑長度）。（3）以k為新考慮的中間

8、點，修改u中各頂點的距離；若從源點v到頂點u（u u）的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修 改后的距離值的頂點k的距離加上邊上的權。（4）重復步驟（2）和（3）直到所冇頂點都包含在s屮。表1算法的計算過程節(jié)點12345610332002302103320200421001450021056000450表1示岀了圖1網(wǎng)中節(jié)點1到其他節(jié)點最短路徑的過程。在表中畫圈的數(shù)字表示 該步驟屮d（v）的最小值。這樣，相應的節(jié)點w就加到n屮，d （v）的值就按耍求更改。 將下面中的程序導入軟件中，調試程序，把輸出的結果截屏。#define max_vertex_num 1

9、00最大頂點數(shù)#include <stdio.h>#include <stdlib.h>#define maxjnt 10000無窮大typedef int adjtype;typedef struct int pi m ax_vertex_num;存放v到vi的一條最矩路徑int end;pathtype;typedef char vtype;設頂點為字符類型typedef structvtype vmax_vertex_num;頂點存儲空間adjtypeamax_vertex_numjlmax_vertex_numj;鄰接矩陣mgraph;鄰接矩陣表示的圖/floy

10、d 算法求網(wǎng)g (用鄰接矩陣表示)中任意兩點間最短路徑/d川是最短路徑長度矩陣，path最短路徑標志矩陣void floyd(mgraph * g,int pathmax_vertex_num,int dmax_vertex_num,int n) int i,j,k;for(i=0;i<n;i+)初始化for(j=0;j<n;j+)if(g->aij<maxnt) pathij=j;elsepathij=-l;diju=g->aij;for(k=0;k<n;k+)進行n次試探for(i=0;i<n;i+)for(j=0;j<n;j+)if(dij

11、>dik+dkj)diju=dik+dkuj;取小者pathiu=pathik;改vi的后繼)int main()int i j,k,v=0,n=6;v為起點，n為頂點個數(shù)mgraph g;int pathmax_vertex_nummax_vertex_num;v到各頂點的最短路徑向量intdmax_vertex_nummax_vertex_num;/v到各頂點最短路徑長度向量/初始化adjtype amax_vertex_nummax_vertex_num= 0,3,3,2,maxn t,max_int,3,0,2,1 ,max_int,max_int,3,2,o,2,max_1nt

12、,max_int,2,1, max_int,0,1,4,max_int,maxn t,2,1,0,5,max_int,max_int,maxn t,4,5,0；for(i=0;i<n;i+)for(j=0;j<n;j+)gaiju=aij;floyd( &gpath,d,6);for(i=0;i<n;i+)/輸出每對頂點間最短路徑長度及最短路徑 for(j=0;j<n;j 卄)printf(nv%d 到 v%d 的最短長度:”,i,j); printf(”df,di|j);輸出vi到vj的最短路徑長度 k=pathij;/jr路徑上 vi 的后續(xù) vk if(k

13、=-i)printf("there is no path between v%d and v%dn”,i,j);路徑不存在else printf("最短路徑為:”);printf(”(v%d”,i);輸出vi的序號iwhile(k!=j)k不等于路徑終點j時printf(,v%d,k);輸出kk=pathkfj;求路徑上下一頂點序號)printf(“,v%d)n”,j);輸出路徑終點序號printf(,n,r);)system(mpause");return 0;)通過對該算法的仔細分析與研究可以得出，上述算法屮有幾點不足之處：(1) 用鄰接矩陣cost來存儲網(wǎng)絡

14、圖，其存儲量為n*n。對于大型稀疏矩陣，這將耗費 大量資源存儲那些無意義的矩陣元素。(2) 當從未標記節(jié)點集合(v-s)選定下一個節(jié)點vj作中間節(jié)點后，在更新操作過程 中，需要掃描所有的未標記節(jié)點并進行比較更新。而未標記節(jié)點集合(v-s) -1 往往包含大量與屮間節(jié)點vj不直接相連的節(jié)點。(3) 在選擇下一個最短路徑節(jié)點作為中間節(jié)點時，需要比較所有的未標記節(jié)點，而 這個屮間節(jié)點往往包含在與已標記節(jié)點s集合的所冇節(jié)點鄰接的節(jié)點屮。(4) 在算法的每次迭代中，由于未標記節(jié)點以無序的形式存放在一個鏈表中或一個 數(shù)組中，每次選擇最短路徑節(jié)點都必須將所有未標記節(jié)點掃描一遍，當節(jié)點數(shù)目很大時, 這無疑將成

15、為制約計算速度的關鍵因素。dijkstra算法用于計算一個源節(jié)點到所有其他節(jié)點的最短代價路徑，它是按路 徑長度遞增的次序來產生最短路徑的算法。假設用帶權的鄰接矩陣cost來表示具有n 個結點的帶權有向圖g3,costi, j表示弧vi,vj的權值，如果從vi到vj不通，則 costi, j二。引進一個輔助向量dist并設vs為起始點，每個分量disti表示已找到的 從起始點vs到每個終點vi的最小權值。則該向量的初始值為:disti=costs, ivi!vo 其屮，v是結點的集合。令s為經找的從起點出發(fā)的最短路徑的終點集合，初始值為 s=vs，則從vs出發(fā)到圖g上其它所有結點vi可能達到的最

16、短路徑長度為 disti二costs, ivi!v。(1) 選擇vj,使得dj=mindi|vi!v-so vj就是當前求得的一條從vs出發(fā)的 最短路徑的終點，令s=svvjo(2) 修改從vs到集合v-s中任意一頂點vk的最短路徑長度。如果 dj+costj, k<dk,則進行第(3)步。(3) 修改 di st k為 di sk k二di st j +cost j, k;重復第 2、3 步操作共 n-l 次,由 此求得從vs到其他頂點的最優(yōu)路徑，該路徑是各權值遞增的序列。改進的dijkstra算法基本思想設置兩個集合s和adj及一個數(shù)組t, s是已標記集合,adj是鄰接點集,t存儲

17、待排序節(jié)點。初始狀態(tài)時,s= vo,t=adjvo,首先,將數(shù)組t通過堆排序調整為小頂堆，取 數(shù)組首元即堆頂節(jié)點current為屮間節(jié)點，并將current加入到已標記集合s屮；再次, 比較更新current的鄰接點集合與已標記集合的差集(adj current-s)中任一節(jié)點vi 的當前最短路徑值。然后杳找s集合所有節(jié)點的鄰接點的并集與s集合的差集(vadjs)-s),同時將 這些節(jié)點順次存入數(shù)組t中,覆蓋原數(shù)組中的節(jié)點，并設置一個計數(shù)器i記錄節(jié)點個數(shù); 最后將數(shù)組屮的前i個元素按它們當前的最短路徑值調整成小頂堆，取堆頂節(jié)點為下一 個最短路徑節(jié)點將其歸并到集合s中。如此反復迭代循環(huán),直到所有

18、的節(jié)點都加入到集 合s屮。傳統(tǒng)dijkstra算法使用的是鄰接矩陣來存儲網(wǎng)絡圖，存儲量為n*n,而使用鄰接表 來存儲網(wǎng)絡數(shù)據(jù)信息，可使存儲空間減少至n量級。另外，利用堆排序來選擇最短路徑節(jié) 點，只處理標記節(jié)點的相鄰節(jié)點，從而大量減少了要計算的節(jié)點數(shù)，最終使得算法的吋間 復雜度由原來的0(n2)降至0(n(logn+e)。隨著網(wǎng)絡中節(jié)點數(shù)目和邊數(shù)的增多，這種改 進的dijkstra算法越來越顯示出英優(yōu)勢，可使算法所需的時間明顯減少,并獲得精度較 高的結杲。岬u啲最短長度：3最翹路徑為：（u4,u2,u0”鈿i的最短長度：2最翹路徑為：（u4,u2,ui114鈿2的最翹長度：0最癒路徑為：0>

19、;4,u2）”鈿3的最更長度：2最短路徑為：（u4,u3）”到u啲最馬長度最更路徑為：（u4,u4”硼的最啟度：0最短路徑為訛45）”5鈿0的最短長度：6最更路徑為電530翊u1的最就度：5最更路徑劃臨憶吐*鈿2的最短長度：5最更路徑為農542*鈿啲最短長度：4最翹路徑為訛53”鈿4的最短長度：5ftg 路徑為：u5,u4)”鈿5的最翹長度：0最想路徑為：0>5,u5詁任意魁續(xù)圖4結果圖4.設計體會通過這次課程設計，讓我更加深刻了解課本知識，和以往對知識的疏忽得以補充, 設計過程中遇到一些模糊的公式和專業(yè)用語，比如說floyd算法、最小生成樹。在使用 參考書時，有的數(shù)據(jù)很難查出，但是這些

20、問題經過這次課程設計，都一一得以解決，我 相信這木書屮還有很多我為搞清楚的問題，但是這次的課程設計給我相當?shù)幕A知識， 為我以后工作打下了嚴實的基礎。雖然這次課程是那么短暫的1周時間，我感覺到這些天我的所學勝過我這一學期 所學，這次任務原則上是設計，其實就是一次大的作業(yè)。在整個的制作過程中，編寫程 序和了解算法原理是最困難的，出于對這些得不熟悉，花費了很多得時間，通過詢問老 師，同學和去圖書館查詢，終于找到了解決的辦法。通信網(wǎng)基礎是通信的專業(yè)課。學好 這門課程對我們在以后得通信學習有著很大得幫助。在我遇到困難的時候，是吳老師和 同學幫助了我，我很感謝他們。通過這次課程設計發(fā)現(xiàn)這其中需要的很多知

21、識我們沒有接觸過，去圖書館杳資料 的吋候發(fā)現(xiàn)我們前邊所學到的僅僅是皮毛，還冇很多需要我們掌握的東西我們根本不知 道。同吋也發(fā)現(xiàn)有很多已經學過的東西我們沒有理解到位，不能靈活運用于實際，不能 很好的用來解決問題，這就需要我們不斷的大量的實踐，通過不斷的口學，不斷地 發(fā)現(xiàn)問題，思考問題，進而解決問題。在這個過程屮我們將深刻理解所學知識，同時也 可以學到不少很實用的東西。，同時讓我對課木知識的鞏固和對基木公式的熟悉和應用, 及熟練使用dijkstra算法用c語言軟件進行計算。使我做事的耐心和仔細程度得以提 高。課程設計是培訓學生運用木專業(yè)所學的理論知識和專業(yè)知識來分析解決實際問題的 重要教學環(huán)節(jié)，是

22、對本學年所學知識的復習和鞏固。同樣，也促使了同學們的相互探討, 相互學習。因此，我們必須認真、謹慎、踏實、一步一步的完成設計。如果時間可以重 來，我可能會認真的去學習和研究，也可能會門己獨立的完成一個項目，我相信無論是 誰看到自己做出的成果時心里一定會很興奮。此次設計讓我明片了一個很深刻的道理： 團隊精神固然很重要，擔人往往還是要靠自己的努力，自己親身去經歷，這樣自己的心 里才會踏實，學到的東西才會更多。課程設計是一個重妾的教學環(huán)節(jié)，通過課程設計使 我們了解到一些實際與理論z間的差異。通過課程設計不僅可以鞏固專業(yè)知識，為以后 的工作打下了堅實的基礎，而其還可以培養(yǎng)和熟練使用資料，運用工具書的能

23、力，把我 們所學的課本知識與實踐結合起來，起到溫故而知新的作用。課程設計誠然是一門專業(yè)課，給我很多專業(yè)知識以及專業(yè)技能上的提升，同吋， 設計讓我感觸很深。使我對抽彖的理論有了具體的認識。在課程設計過程中。以設計 任務書的指導思想為屮心，參照冇關資料，冇計劃冇頭緒、冇邏輯地把這次設計搞好! 總z,這次課程設計使我收獲很多、學會很多、比以往更有耐心很多。感謝學校及老師 給我們這次課程設計的機會，最真摯的感謝我們的輔導老師，在設計過程中，老師精心 的輔導和不厭英煩地的態(tài)度才使得我們以順利的完成這次設計，同時也增加我們對知識 的追求和欲望度。短暫的一個星期過去了，我完成了門己的通信網(wǎng)基礎課程設計，雖然 在這過程中遇到了許多得困難，但成功還是給我?guī)砹烁说孟矏?。相信我得通信網(wǎng)學 習之路不會就此結