歡迎來到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁 裝配圖網(wǎng) > 資源分類 > DOC文檔下載  

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問題實(shí)驗(yàn)報(bào)告

  • 資源ID:23624788       資源大?。?span id="nltc328" class="font-tahoma">239.91KB        全文頁數(shù):17頁
  • 資源格式: DOC        下載積分:9.9積分
快捷下載 游客一鍵下載
會員登錄下載
微信登錄下載
三方登錄下載: 微信開放平臺登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要9.9積分
郵箱/手機(jī):
溫馨提示:
用戶名和密碼都是您填寫的郵箱或者手機(jī)號,方便查詢和重復(fù)下載(系統(tǒng)自動生成)
支付方式: 支付寶    微信支付   
驗(yàn)證碼:   換一換

 
賬號:
密碼:
驗(yàn)證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會被瀏覽器默認(rèn)打開,此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無水印,預(yù)覽文檔經(jīng)過壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒有明確說明有答案則都視為沒有答案,請知曉。

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問題實(shí)驗(yàn)報(bào)告

目 錄 一、概述1二、系統(tǒng)分析1三、概要設(shè)計(jì)2四、詳細(xì)設(shè)計(jì)54.1建立圖的存儲結(jié)構(gòu)54.2單源最短路徑64.3任意一對頂點(diǎn)之間的最短路徑7五、運(yùn)行與測試8參考文獻(xiàn)11附錄12交通咨詢系統(tǒng)設(shè)計(jì)(最短路徑問題)一、概述 在交通網(wǎng)絡(luò)日益發(fā)達(dá)的今天,針對人們關(guān)心的各種問題,利用計(jì)算機(jī)建立一個交通咨詢系統(tǒng)。在系統(tǒng)中采用圖來構(gòu)造各個城市之間的聯(lián)系,圖中頂點(diǎn)表示城市,邊表示各個城市之間的交通關(guān)系,所帶權(quán)值為兩個城市間的耗費(fèi)。這個交通咨詢系統(tǒng)可以回答旅客提出的各種問題,例如:如何選擇一條路徑使得從A城到B城途中中轉(zhuǎn)次數(shù)最少;如何選擇一條路徑使得從A城到B城里程最短;如何選擇一條路徑使得從A城到B城花費(fèi)最低等等的一系列問題。二、系統(tǒng)分析設(shè)計(jì)一個交通咨詢系統(tǒng),能咨詢從任何一個城市頂點(diǎn)到另一城市頂點(diǎn)之間的最短路徑(里程)、最低花費(fèi)或是最少時間等問題。對于不同的咨詢要求,可輸入城市間的路程、所需時間或是所需費(fèi)用等信息。針對最短路徑問題,在本系統(tǒng)中采用圖的相關(guān)知識,以解決在實(shí)際情況中的最短路徑問題,本系統(tǒng)中包括了建立圖的存儲結(jié)構(gòu)、單源最短問題、對任意一對頂點(diǎn)間最短路徑問題三個問題,這對以上幾個問題采用了迪杰斯特拉算法和弗洛伊德算法。并未本系統(tǒng)設(shè)置一人性化的系統(tǒng)提示菜單,方便使用者的使用。三、概要設(shè)計(jì)可以將該系統(tǒng)大致分為三個部分: 1 建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu);2 解決單源最短路徑問題;3 實(shí)現(xiàn)兩個城市頂點(diǎn)之間的最短路徑問題。交通咨詢系統(tǒng)迪杰斯特拉算法(單源最短路徑)費(fèi)洛依德算法(任意頂點(diǎn)對間最短路徑)建立圖的存儲結(jié)構(gòu)義迪杰斯特拉算法流圖:弗洛伊德算法流圖:四、詳細(xì)設(shè)計(jì) 4.1建立圖的存儲結(jié)構(gòu)定義交通圖的存儲結(jié)構(gòu)。鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n個頂點(diǎn)的圖,則G的鄰接矩陣是具有如下定義的n階方陣。注:一個圖的鄰接矩陣表示是唯一的!其表示需要用一個二維數(shù)組存儲頂點(diǎn)之間相鄰關(guān)系的鄰接矩陣并且還需要用一個具有n個元素的一維數(shù)組來存儲頂點(diǎn)信息(下標(biāo)為i的元素存儲頂點(diǎn)的信息)。鄰接矩陣的存儲結(jié)構(gòu):#define MVNum 100 /最大頂點(diǎn)數(shù)typedef struct VertexType vexsMVNum;/頂點(diǎn)數(shù)組,類型假定為char型 Adjmatrix arcsMVNumMVNum;/鄰接矩陣,假定為int型MGraph;注:由于有向圖的鄰接矩陣是不對稱的,故程序運(yùn)行時只需要輸入所有有向邊及其權(quán)值即可。4.2單源最短路徑單源最短路徑問題:已知有向圖(帶權(quán)),期望找出從某個源點(diǎn)SV到G中其余各頂點(diǎn)的最短路徑。迪杰斯特拉算法即按路徑長度遞增產(chǎn)生諸頂點(diǎn)的最短路徑算法。算法思想:設(shè)有向圖G=(V,E),其中V=1,2,n,cost是表示G的鄰接矩陣, costij表示有向邊<i,j>的權(quán)。若不存在有向邊<i,j>,則costij 的權(quán)為無窮大(這里取值為32767)。設(shè)S是一個集合,集合中一個元素表示一個頂點(diǎn),從源點(diǎn)到這些頂點(diǎn)的最短距離已經(jīng)求出。設(shè)頂點(diǎn)V1為源點(diǎn),集合S的初態(tài)只包含頂點(diǎn)V1。數(shù)組dist記錄從源點(diǎn)到其它各頂點(diǎn)當(dāng)前的最短距離,其初值為disti= costij,i=2,n。從S之外的頂點(diǎn)集合V-S中選出一個頂點(diǎn)w,使distw 的值最小。于是從源點(diǎn)到達(dá)w只通過S中的頂點(diǎn),把w加入集合S中,調(diào)整dist中記錄的從源點(diǎn)到V-S中每個頂點(diǎn)v的距離:從原來的distv和distw+costwv中選擇較小的值作為新的distv。重復(fù)上述過程,直到S中包含V中其余頂點(diǎn)的最短路徑。 最終結(jié)果是:S記錄了從源點(diǎn)到該頂點(diǎn)存在最短路徑的頂點(diǎn)集合,數(shù)組dist記錄了從源點(diǎn)到V中其余各頂點(diǎn)之間的最短路徑,path是最短路徑的路徑數(shù)組,其中pathi表示從源點(diǎn)到頂點(diǎn)i之間的最短路徑的前驅(qū)頂點(diǎn)。 4.3任意一對頂點(diǎn)之間的最短路徑 任意頂點(diǎn)對之間的最短路徑問題,是對于給定的有向網(wǎng)絡(luò)圖G=(V,E),要對G中任意一對頂點(diǎn)有序?qū)?,“V,W(VW)”,找出V到W的最短路徑。而要解決這個問題,可以依次把有向網(wǎng)絡(luò)圖中每個頂點(diǎn)作為源點(diǎn),重復(fù)執(zhí)行前面的迪杰斯特拉算法n次,即可求得每對之間的最短路徑。 費(fèi)洛伊德算法的基本思想:假設(shè)求從Vi到Vj的最短路徑。如果存在一條長度為arcsij的路徑,該路徑不一定是最短路徑,還需要進(jìn)行n次試探。首先考慮路徑<vi,v1>和<v1,vj>是否存在。如果存在,則比較路徑<vi.vj>和<vi,v1,vj>的路徑長度,取長度較短者為當(dāng)前所求得。該路徑是中間頂點(diǎn)序號不大于1的最短路徑。其次,考慮從vi到vj是否包含有頂點(diǎn)v2為中間頂點(diǎn)的路徑< vi,v2,vj>,若沒有,則說明從vi到vj的當(dāng)前最短路徑就是前一步求出的;若有,那么<vi,v2,vj>可分解為<vi,v2>和<v2,vj>,而這兩條路徑是前一次找到的中間點(diǎn)序號不大于1的最短路徑,將這兩條路徑長度相加就得到路徑<vi,v2,vj>的長度。將該長度與前一次中求得的從vi到vj的中間頂點(diǎn)序號不大于1的最短路徑比較,取其長度較短者作為當(dāng)前求得的從vi到vj的中間頂點(diǎn)序號不大于2的最短路徑。依此類推直至頂點(diǎn)vn加入當(dāng)前從vi到vj的最短路徑后,選出從vi到vj的中間頂點(diǎn)序號不大于n的最短路徑為止。由于圖G中頂點(diǎn)序號不大于n,所以vi到vj的中間頂點(diǎn)序號不大于n的最短路徑,已考慮了所有頂點(diǎn)作為中間頂點(diǎn)的可能性,因此,它就是vi到vj的最短路徑。五、運(yùn)行與測試3測試實(shí)例1:利用如下圖所示的有向圖來測試131771 61747632646456262455測試實(shí)例2:利用下圖求交通網(wǎng)絡(luò)圖(無向圖)的最短路徑。2553北京西安70416952349徐州成都51181234鄭州515796512368上海13857廣州6實(shí)例1運(yùn)行結(jié)果:實(shí)例2運(yùn)行結(jié)果:六、總結(jié)與心得該課程設(shè)計(jì)主要是從日常生活中經(jīng)常遇到的交通網(wǎng)絡(luò)問題入手,進(jìn)而利用計(jì)算機(jī)去建立一個交通咨詢系統(tǒng),以處理和解決旅客們關(guān)心的各種問題(當(dāng)然此次試驗(yàn)最終主要解決的問題是:最短路徑問題)。這次試驗(yàn)中我深刻的了解到了樹在計(jì)算機(jī)中的應(yīng)用是如何的神奇與靈活,對于很多的問題我們可以通過樹的相關(guān)知識來解決,特別是在解決最短路徑問題中,顯得尤為重要。經(jīng)過著次實(shí)驗(yàn),我了解到了關(guān)于樹的有關(guān)算法,如:迪杰斯特拉算法、弗洛伊德算法等,對樹的學(xué)習(xí)有了一個更深的了解。參考文獻(xiàn)【1】數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏.清華大學(xué)出版社.【2】數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)蘇仕華.極械工業(yè)出版社.附錄#include<stdio.h>#include<stdlib.h>#define MVNum 100#define Maxint 32767enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum;void CreateMGraph(MGraph * G,int n,int e)int i,j,k,w;for(i=1;i<=n;i+)G->vexsi=(char)i;for(i=1;i<=n;i+)for(j=1;j<=n;j+)G->arcsij=Maxint;printf("輸入%d條邊的i.j及w:n",e);for(k=1;k<=e;k+)scanf("%d,%d,%d",&i,&j,&w);G->arcsij=w;printf("有向圖的存儲結(jié)構(gòu)建立完畢!n");void Dijkstra(MGraph *G,int v1,int n)int D2MVNum,p2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;v<=n;v+)Sv=FALSE; D2v=G->arcsv1v; if(D2v<Maxint) p2v=v1;else p2v=0;D2v1=0; Sv1=TRUE;for(i=2;i<n;i+)min=Maxint;for(w=1;w<=n;w+)if(!Sw && D2w<min)v=w;min=D2w;Sv=TRUE;for(w=1;w<=n;w+)if(!Sw && (D2v+G->arcsvw<D2w)D2w=D2v+G->arcsvw;p2w=v;printf("路徑長度 路徑n");for(i=1;i<=n;i+)printf("%5d",D2i);printf("%5d",i);v=p2i;while(v!=0)printf("<-%d",v);v=p2v;printf("n");void Floyd(MGraph *G,int n)int i,j,k,v,w;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if( G->arcsij!=Maxint)pij=j;elsepij=0;Dij=G->arcsij;for(k=1;k<=n;k+)for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(Dik+Dkj<Dij) Dij=Dik+Dkj;pij=pik;void main()MGraph *G;int m,n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf("輸入圖中頂點(diǎn)個數(shù)和邊數(shù)n,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);while(xz!=0)printf("*求城市之間最短路徑*n");printf("=n");printf("1.求一個城市到所有城市的最短路徑n");printf("2.求任意的兩個城市之間的最短路徑n");printf("=n");printf("請選擇 :1或2,選擇0退出:n");scanf("%d",&xz);if (xz=2)Floyd(G,n);printf("輸入源點(diǎn)(或起點(diǎn))和終點(diǎn):v,w:");scanf("%d,%d",&v,&w);k=pvw;if (k=0)printf("頂點(diǎn)%d 到 %d 無路徑!n",v,w);elseprintf("從頂點(diǎn)%d 到 %d 最短路徑路徑是:%d",v,w,v);while (k!=w)printf("-%d",k);k=pkw;printf("-%d",w);printf("徑路長度:%dn",Dvw);else if(xz=1)printf("求單源路徑,輸入源點(diǎn)v :");scanf("%d",&v);Dijkstra(G,v,n);printf("結(jié)束求最短路徑,再見!n");

注意事項(xiàng)

本文(《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問題實(shí)驗(yàn)報(bào)告)為本站會員(jun****875)主動上傳,裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng)(點(diǎn)擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因?yàn)榫W(wǎng)速或其他原因下載失敗請重新下載,重復(fù)下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!