數(shù)據(jù)結構課程設計報告--Dijkstra算法求最短路徑

1、中南大學數(shù)據(jù)結構課程設計題目第9題Dijkstra算法求最短路徑學生姓名XXXX指導教師XXXX學院信息科學與工程學院專業(yè)班級XXXXXXX完成時間XXXXXXX目錄第一章問題分析與任務定義31.1 課程設計題目31.2 原始數(shù)據(jù)的輸入格式31.3 實現(xiàn)功能31.4 測試用例31.5 問題分析3第二章數(shù)據(jù)結構的選擇和概要設計41 數(shù)據(jù)結構的選擇41 概要設計4第三章詳細設計與編碼63.4 框架的建立63.5 點結構體的定義73.6 創(chuàng)立帶權值有向圖83.7 鄰接矩陣的顯示93.8 遞歸函數(shù)的應用103.9 Dijkstra算法實現(xiàn)最短路徑10第四章上機調試11記錄調試過程中錯誤和問題的處理11

2、算法的時間課空間性能分析11算法的設計、調試經驗和體會11第五章測試Z果12第六章學習心彳#體會12第七章參考文獻12附錄12第一章問題分析與任務定義1、課程設計題目：題目：采用適當?shù)拇鎯Y構實現(xiàn)帶權有向圖的存儲，建立，輸入、顯示，以及使用Dijkstra算法，尋找和輸出帶權有向圖中某個源點到其余各點的最短路徑要求：采用適當?shù)拇鎯Y構實現(xiàn)帶權有向圖的存儲，建立，輸入、顯示，以及使用Dijkstra算法。具體任務：建立圖的存儲模塊，建立圖的輸出模塊，在建圖后從單源點開始求最短路徑，并顯示出來。.原始數(shù)據(jù)的輸入格式建圖：2.1.1數(shù)字顯示：2.2.1數(shù)字+逗號+數(shù)字+回車2.2.2字母+回車.實現(xiàn)

3、功能建立有向圖顯示存儲的有向圖顯示從頂點到其他各個頂點的最短路徑和是否存在路徑.測試用例正確數(shù)據(jù)：輸入頂點；邊值信息輸出結果：最短路徑是否存在，存在的情況最短路徑是多少，其次是不存在。.問題分析實現(xiàn)本程序要解決以下幾個問題：如何存儲一個有向圖。如何在界面中輸出該有向圖如何定義起始源點。如何選擇出最短路徑。找到的最短路徑如何輸出。第二章數(shù)據(jù)結構的選擇和概要設計.數(shù)據(jù)結構的選擇：在圖的結構中，任意兩個頂點之間都可能存在關系，比線性表和樹要復雜。由于不存在嚴格的前后順序，因而不能采用簡單的數(shù)組來存儲圖；另一方面，如果采用鏈表，由于圖中各頂點的度數(shù)不盡相同，最小度數(shù)和最大度數(shù)可能相差很大，如果按最大度

4、數(shù)的頂點來設計鏈表的指針域，則會浪費很多存儲單元，反之，如果按照各個頂點設計不同的鏈表結點，則會給操作帶來很大的困難。在此我選用鄰接矩陣的存儲結構。采用鄰接矩陣存儲，很容易判斷圖中兩個頂點是否相連，也容易求出各個頂點的度。不過任何事情都不是完美的，采用鄰接矩陣存儲圖時，測試其邊的數(shù)目，必須檢查邊二維數(shù)組的所有元素，時間復雜度為O（n2）,這對于頂點很多而邊較少的圖（稀疏圖）是非常不合算的。以鄰接矩陣存儲有向圖。.概要設計對于最短路徑問題：最短路徑是在實際應用中非常有用的工具，我們常見的兩種最短路徑是：（1）從某源點到其余各頂點之間的最短路徑。（2）每一段頂點之間的最短路徑在這里我們解決第一類問

5、題。Dijkstra算法用于求最短路徑：Dijkstra算法是按路徑長度遞增的次序逐步產生源點到其他頂點問的最短路徑。算法建立一個頂點集合S,初始時該集合只有源點V0,然后逐步將已求得最短路徑的頂點加入到集合中，直到全部頂點都在集合S中，算法結束。2.3Dijkstra算法思想設costi,j=0,S為已經求得最短路徑的頂點集合，distancei數(shù)組的每個元素表示當前狀態(tài)下源點V0到Vi的最短路徑。算法如下：1）初始化：S=V0,distancei=cost0,i。2）選擇一個終點Vj,滿足distancej=MINdistancei|ViCV-S。3）把Vj加入到S中。4）修改distan

6、ce數(shù)組元素，修改邏輯為對于所有不在S中的頂點Vi.if(distancej+costi,j<distancej+costi,jdistancei)distancei=5）重復操作2）、3）、4）,直到全部頂點加入到S中2.4實現(xiàn)流程在任意圖中實現(xiàn)求最短路徑問題，第一步是要能成功的在內存中輸入圖的信息，圖的信息有兩個，一是頂點個數(shù)，二是每兩點之間的權值信息。當建立圖之后，對圖進行遍歷才能使用Dijkstra算法求出最短路徑；在完成了圖的建立之后，用Dijkstra算法的思想，從單源點開始，求出到各個頂點的最短路徑，并能夠實現(xiàn)顯示功能。程序流程圖：(1)輸入頂點個數(shù)n,邊的條數(shù)，初始化鄰接

7、矩陣。(2)初始化所每條邊的權值與Dh中(3)找出v0到圖中其他各點的最小值經過改最小值的點到除它外其他各點的最小值直到s中的所有值全部被處理過，(4)輸出各最短路徑的長度Dw算法的思想，從單源點開始，求出到各個頂點的最短路徑，并能夠實現(xiàn)顯示功能。第三章詳細設計和編碼框架的建立typedefcharVertexType;/定義圖的頂點為字符型typedefintVRType;/頂點關系類型typedefintInfoType;/該弧相關信息typedefstructArcCellVRTypeadj;/權值InfoType*info;/弧相關信息的指針ArcCell;typedefstructV

8、ertexTypevexsMAX_VERTEX_NUM;/L維數(shù)組，存儲頂點ArcCellarcsMAX_VERTEX_NUMMAX_VERTEX_NUMW矩陣：二維數(shù)組,存儲邊和弧intvexnum,arcnum;/圖的當前頂點數(shù)和弧數(shù)MGrph;/鄰接矩陣表示的圖頂點的定義typedefcharVertexType;/定義圖的頂點為字符型頂點的最大個數(shù)25ArcCellarcsMAX_VERTEX_NUMMAX_VERTEX_NUM軸數(shù)組用于存放令口接矩陣，每個位置代表而值為圖中而權值，其余用無窮大3000表示。點結構體的定義/*確定位置函數(shù)*/intLocateVex(MGrph*G,V

9、ertexTypev)intj,b;for(b=0;b<G->vexnum;b+)/在所有頂點中尋找if(G->vexsb=v)找到所找的頂點在b位置j=b;break;/ifreturn(j);/LocateVex創(chuàng)立帶權值有向圖首先輸入該有向圖的頂點數(shù)n,然后依次輸入各個頂點及邊長(輸入的頂點的序號應該小于頂點的數(shù)目)。/*有向圖的建立*/voidCreat_YG(MGrph*G)(inti,k,j,n;VertexTypev1,v2;intw=1;printf("請輸入頂點個數(shù)和弧數(shù)如括號里白方式(3,3):");/讀入頂點個數(shù)和弧的個數(shù)scanf(

10、"%d,%d",&G->vexnum,&G->arcnum);/讀出邊和弧的信息printf("n");/換行輸出for(i=0;i<G->vexnum;i+)(printf("請輸入圖的第%d個頂點：",w);/輸入指定的頂點w+;fflush(stdin);scanf("%c",&G->vexsi);printf("n");for(i=0;i<G->vexnum;i+)for(j=0;j<G->vexnum;j+)

11、(G->arcsij.adj=INFINITY;G->=NULL;for(k=0;k<G->arcnum;k+)輸入各弧并構造鄰接矩陣printf("請輸入邊的起點和終點和權值如(v1,v2,n):");/起始點和終點和兩點之間對應的權值fflush(stdin);scanf("%c,%c,%d”,&v1,&v2,&n);printf("n");i=LocateVex(G,v1);/確定v1的位置j=LocateVex(G,v2);/確定v2的位置G->arcs皿.ad

12、j=n;/邊<v1,v2>的權值賦為1,如需要權值操作則相應修改一下即可G->=NULL;/如需要有相關信息則相對應輸入，在這里我設置為空第二個forgetchar();/Creat_YGvoidjuzhen(MGrph*G)/用矩陣來存儲并顯示出結果inti,j,k;printf("鄰接矩陣顯示：n");printf("t");for(i=0;i<G->vexnum;i+)printf("t%5c”,G->vexsi);for(j=0;j<G->vexnum;j+)prin

13、tf("nn");printf("t%5c”,G->vexsj);for(k=0;k<G->vexnum;k+)if(G->arcsjk.adj<INFINITY)printf("t%5d”,G->arcs皿k.adj);elseprintf("t3000");/無權值的直接輸出最大值鄰接矩陣的顯示在圖的鄰接矩陣顯示中，分別利用for循環(huán)輸出了矩陣的行列標，使矩陣很明了。voidjuzhen(MGrph*G)/用矩陣來存儲并顯示出結果inti,j,k;printf("鄰接矩陣顯示：n&qu

14、ot;);printf("t");for(i=0;i<G->vexnum;i+)printf("t%5c”,G->vexsi);for(j=0;j<G->vexnum;j+)printf("nn");printf("t%5c”,G->vexsj);for(k=0;k<G->vexnum;k+)if(G->arcsjk.adj<INFINITY)printf("t%5d",G->arcsjk.adj);elseprintf("t3000&qu

15、ot;);/無權值的直接輸出最大值)遞歸函數(shù)應用思想是patn數(shù)組來表示前驅頂點的位置，然后遞歸輸出每個頂點的前驅voidShort(MGrph*G,intpath,inti,intw)遞歸函數(shù)是用來輸出從源點出發(fā)到終點之前的頂點思想是patn數(shù)組來表示前驅頂點的位置，然后遞歸輸出每個頂點的前驅intk;k=pathi;if(k!=w)Short(G,path,k,w);printf("%c,",G->vexsk);/輸出k位置的頂點值)Dijkstra算法實現(xiàn)最短路徑設圖以鄰接矩陣cost存儲，矩陣中各元素的值為各邊的權值。頂點間無邊時其對應權信用無窮大表示。從頂點

16、V0到其它各頂點間的最短路徑的具體步驟如下：a)變量定義：定義整型數(shù)組S,這是一個頂點集合，初始時該集合只有源點v0,然后逐步將以求得最短路徑的頂點加入到該集合中，直到全部頂點都在集合S中，算法結束。定義兩個整型變量dis、mindis均用來標志圖中最短的那一條路徑。b)初始化：初始化dist數(shù)組的值即為cost數(shù)組中存放的權值。disti=costv0i初始化求到每個頂點的最短路徑時都經過v0頂點。pathi.pnode0=v0初始化記錄經過的頂點數(shù)都為0。pathi.num=0;初始化頂點集合s為空，即還未開始。si=0;c)源點的選擇：將V0頂點加入到頂點集合s中。sv0=1d)利用fo

17、r循環(huán)選擇一個終點Vj,使其滿足V0到Vj距離最短，同時將Vj加入集合S中。e)根據(jù)j頂點調整當前的最短路徑，若滿足disti>distj+costji,則修改disti的值。同時V0到Vi的最短路徑中經過的頂點數(shù)加1,即pathi.num+;并將經過的頂點存入數(shù)組pnode即pathi.pnodepathi.num=jf)此時一趟求最短路徑完畢，將終點V1添加到路徑中。g)循環(huán)執(zhí)行d),e),f)操作，直到全部頂點加入到S中。第四章上機調試記錄調試過程中錯誤和問題的處理1)當輸入格式不符合程序要求時，會出現(xiàn)循環(huán)2)當兩頂點間沒有路徑時，權值為無窮大，但在本程序中只能用一個具體的數(shù)字20

18、00代替抽象的無窮大。3)在程序的調試過程可暫時多加一些輸出語句以便及時查看一下中間運行情況，并對程序規(guī)格說明作調整和改動。算法的時間和空間性能分析時間復雜度對于n個頂點的有向圖，求一個頂點到其他頂點的最短路徑的時間為O(n),調整最短路徑的循環(huán)共執(zhí)行n-1次，是二層循環(huán)，所以，時間復雜度是O(n2)。空間復雜度采用鄰接矩陣存儲有向圖，應處理每兩個頂點之間的關系，所以空間復雜度為O(n2)。算法設計、調試的經驗和體會Dijkstra算法在上課的時候曾作為重點講過，所以在做查找最短路徑的算法時很流暢，但是在輸出最短路徑的時候遇到了很大的阻力。因為在定義結點時，使用的是結構體數(shù)組，所以當處理V0到

19、每個結點的最短路徑時，導致無法具體記錄經過的頂點數(shù)，只能記錄源點、終點前一頂點以及終點。所以本程序在輸出最短路徑時有較大的瑕疵，還需進一步修改。第五章測試結果5.1測試結果:注意問題：1、輸入頂點個數(shù)：最大不超過25,請輸入羅馬數(shù)字，若輸入其他符號，無意義；2、以“字母字母數(shù)字”的格式輸入圖的信息，輸入第一個字母為原點，第二個字母為終點，輸入“數(shù)字”為權值，最后輸入一個“字母”為頂點輸入。輸入完成；3、在輸入完成后，屏幕顯示鄰接矩陣與最短路徑。第六章學習心得體會通過對本次課程設計的學習與交流，使我學習到一部分很重要的關于編程方面思想，同時也獲得了部分學習其他學科的方法。學習重在于體會，體會這種

20、學科給我?guī)淼乃伎?，給我?guī)碛蓽\入深的演算心得。做一次課程設計，不僅僅是為了完成某項任務，而在于是否能從這次任務中總結出一些處理同類任務的方法和技巧。每次全力的付出，都會有或多或少的收獲。通過對本次課程設計涉及的問題的分析和處理，了解到學習數(shù)據(jù)結構對編程的技巧和思想方法。以前也了解過數(shù)據(jù)結構相關的書籍，但沒有深入的學習，本次上機課程設計從選題上也把學習的方法應用其中，在編程時算法的理解和分析十分重要，首先的弄懂它的基本框架，用什么來算法來實現(xiàn)，最后通過查找部分資料，修改調試，總結心得，就是一種進步。第七章參考文獻:嚴蔚敏吳偉明編著的數(shù)據(jù)結構（C語言版）:楊曉波主編王弘王聰華胡永副主編的數(shù)據(jù)結構

21、實驗指導（C語言版）附件：#include<stdio.h>#include<stdlib.h>#defineMAX_VERTEX_NUM25/最大頂點個數(shù)#defineINFINITY3000/最大值typedefcharVertexType;/定義圖的頂點為字符型typedefintVRType;/頂點關系類型typedefintInfoType;/該弧相關信息typedefstructArcCellVRTypeadj;/權值InfoType*info;弧相關信息的指針ArcCell;typedefstructVertexTypevexsMAX_VERTEX_NUM

22、;/一維數(shù)組，存儲頂點ArcCellarcsMAX_VERTEX_NUMMAX_VERTEX_NUM;鄰接矩陣：二維數(shù)組，存儲邊和弧intvexnum,arcnum;/圖的當前頂點數(shù)和弧數(shù)MGrph;鄰接矩陣表示的圖/*確定位置函數(shù)*/intLocateVex(MGrph*G,VertexTypev)intj,b;for(b=0;b<G->vexnum;b+)/在所有頂點中尋找if(G->vexsb=v)找到所找的頂點在b位置j=b;break;/ifreturn(j);/LocateVex/*有向圖的建立*/voidCreat_YG(MGrph*G)inti,k,j,n;V

23、ertexTypev1,v2;intw=1;printf("請輸入頂點個數(shù)和弧數(shù)如括號里白方式(3,3):");/讀入頂點個數(shù)和弧的個數(shù)scanf("%d,%d",&G->vexnum,&G->arcnum);/讀出邊和弧的信息printf("n");/換行輸出for(i=0;i<G->vexnum;i+)printf("請輸入圖的第%d個頂點：",w);/輸入指定的頂點w+;fflush(stdin);scanf("%c",&G->vexs

24、i);printf("n");for(i=0;i<G->vexnum;i+)for(j=0;j<G->vexnum;j+)G->arcsij.adj=INFINITY;G->=NULL;for(k=0;k<G->arcnum;k+)輸入各弧并構造鄰接矩陣printf("請輸入邊的起點和終點和權值如(v1,v2,n):");起始點和終點和兩點之間對應的權值fflush(stdin);scanf("%c,%c,%d",&v1,&v2,&n);pr

25、intf("n");i=LocateVex(G,v1);確定v1的位置j=LocateVex(G,v2);確定v2的位置G->arcsij.adj=n;/邊71,丫2>的權值賦為1,如需要權值操作則相應修改一下即可G->=NULL;/如需要有相關信息則相對應輸入，在這里我設置為空第二個forgetchar();/Creat_YGvoidjuzhen(MGrph*G)/用矩陣來存儲并顯示出結果inti,j,k;printf("鄰接矩陣顯示：n");printf("t");for(i=0;i<

26、G->vexnum;i+)printf("t%5c",G->vexsi);for(j=0;j<G->vexnum;j+)printf("nn");printf("t%5c",G->vexsj);for(k=0;k<G->vexnum;k+)if(G->arcsjk.adj<INFINITY)printf("t%5d",G->arcsjk.adj);elseprintf("t3000");/無權值的直接輸出最大值voidShort(MGr

27、ph*G,intpath口,inti,intw)遞歸函數(shù)是用來輸出從源點出發(fā)到終點之前的頂點思想是patn數(shù)組來表示前驅頂點的位置，然后遞歸輸出每個頂點的前驅intk;k=pathi;if(k!=w)Short(G,path,k,w);printf("%c,",G->vexsk);輸出k位置的頂點值)voidShortestPath(MGrph*G,intw)/Dijkstrs算法應用inti,k,m,n,min;intfinal30,path30,D30;定義三個數(shù)組，final標記該頂點是否在最短路徑上/path口用來記錄頂點的前驅頂點的位置，D口是用來記錄從源點到該點的最短路徑長度for(i=0;i<G->vexnum;i+)pathi=w;/首先把所有頂點的前驅頂點的位置賦值為w位置，也就