迪克斯特拉算法報告.doc

《迪克斯特拉算法報告.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、姓名：楊網(wǎng)學(xué)號：3090811022班級：計算091迪克斯特拉算法報告問題描述：以圖所示的有向帶權(quán)圖為例設(shè)計測試上述Dijkstra函數(shù)的程序?；疽螅海?）初始狀態(tài)時若從源點v0到某下標為i的結(jié)點有邊，則distance[i]為該邊的權(quán)值，且令path[i]為源點v0;若從源點v0到下標為i的結(jié)點無邊，則distance[i]為最大權(quán)值MaxWeight，且令distance[i]為-1。（2）函數(shù)設(shè)計成一個循環(huán)迭代過程。（3）數(shù)組path中存放了從源點v0到其他各個節(jié)點的最短路徑的前一個結(jié)點的下標。測試數(shù)據(jù)：chara[]={‘A’,’B’,’C’,’D’,’E’,’F’};r

2、cw[]={{0,2,5},{0,3,30},{1,0,2},{1,4,8},{2,1,15},{2,5,7},{4,3,4},{5,3,10},{5,4,18}};算法思想：設(shè)置兩個接點的集合S和T，集合S中存放已找到最短路徑的接點，集合T中存放當(dāng)前還未找到最短路徑的接點。初始態(tài)時，集合S中只包含源點，設(shè)置v0，然后不斷從集合T中選擇到原點v0路徑長度最短的接點u加入到集合S中，集合S中沒加入一個新的接點u都要修改從源點v0到集合T中剩余接點的當(dāng)前最短路徑長度值，集合T中各接點的新的當(dāng)前最短路徑長度值，為原來最短路徑長度值與從源點到過結(jié)點u到底該節(jié)點的路徑長度中的較小者。此過程不斷

3、重復(fù)，直到集合T中的接點全部加入集合S中為止。模塊劃分：(1)voidCreateGraph(AdjMGraph*G,DataTypeV[],intn,RowColWeightE[],inte);在圖G中插入n個結(jié)點信息V和e條邊信息E(2)voidDijkstra(AdjMGraphG,intv0,intdistance[],intpath[]);求最短路徑。(3)voidmain(void)，主函數(shù)。調(diào)用函數(shù)Initiate()和函數(shù)Dijkstra()數(shù)據(jù)結(jié)構(gòu)：typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;typede

4、fstruct{introw;intcol;intweight;}RowColWeight;typedefstruct{SeqListVertices;intedge[MaxVertices][MaxVertices];intnumOfEdges;}AdjMGraph;源程序：typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;//初始化ListInitiate(L)voidListInitiate(SeqList*L)//初始化順序表{L->size=0;//定義初始元素個數(shù)}//求當(dāng)前數(shù)據(jù)元素個數(shù)ListLength(L)in

5、tListLength(SeqListL)//返回順序表L的當(dāng)前數(shù)據(jù)元素個數(shù){returnL.size;}//插入數(shù)據(jù)元素ListInsert(L,i,x)intListInsert(SeqList*L,inti,DataTypex)//在順序表L的第i個位置前插入數(shù)據(jù)元素值X//插入成功返回1,失敗返回0{intj;if(L->size>=MaxSize){printf("順序表已滿無法插入！");return0;}elseif(i<0

6、

7、i>L->size){printf("參數(shù)i不合法！");return0;}else{//未插入做準備for(j=L->size;j>i

8、;j--)L->list[j]=L->list[j-1];L->list[i]=x;//插入xL->size++;return1;}}//刪除數(shù)據(jù)元素ListDelete(L,i,x)intListDelete(SeqList*L,inti,DataType*x)//刪除順序表{intj;if(L->size<=0){printf("順序表已空無數(shù)據(jù)元素可刪！");return0;}elseif(i<0

9、

10、i>L->size-1){printf("參數(shù)i不合法!");return0;}else{*x=L->list[i];for(j=i+1;j<=L->size-1;j++)

11、L->list[j-1]=L->list[j];L->size--;return1;}}//取數(shù)據(jù)元素LiseGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i<0

12、

13、i>L.size-1){printf("參數(shù)i不合法！");return0;}else{*x=L.list[i];return1;}}voidDijkstra(AdjMGraphG,intv0,intdistance[],intpath