《數(shù)據(jù)結(jié)構(gòu)教學(xué)規(guī)劃》最短路徑問(wèn)答實(shí)驗(yàn)報(bào)告

~目 錄一、概述 1二、系統(tǒng)分析 1三、概要設(shè)計(jì) 2四、詳細(xì)設(shè)計(jì) 54.1建立圖的存儲(chǔ)結(jié)構(gòu) 54.2單源最短路徑 64.3任意一對(duì)頂點(diǎn)之間的最短路徑 7五、運(yùn)行與測(cè)試 8參考文獻(xiàn) 11附錄 12~交通咨詢系統(tǒng)設(shè)計(jì)（最短路徑問(wèn)題）一、概述在交通網(wǎng)絡(luò)日益發(fā)達(dá)的今天，針對(duì)人們關(guān)心的各種問(wèn)題，利用計(jì)感謝閱讀算機(jī)建立一個(gè)交通咨詢系統(tǒng)。在系統(tǒng)中采用圖來(lái)構(gòu)造各個(gè)城市之間的精品文檔放心下載聯(lián)系，圖中頂點(diǎn)表示城市，邊表示各個(gè)城市之間的交通關(guān)系，所帶權(quán)精品文檔放心下載值為兩個(gè)城市間的耗費(fèi)。這個(gè)交通咨詢系統(tǒng)可以回答旅客提出的各種謝謝閱讀問(wèn)題，例如：如何選擇一條路徑使得從A城到B城途中中轉(zhuǎn)次數(shù)最少；感謝閱讀如何選擇一條路徑使得從A城到B城里程最短；如何選擇一條路徑使精品文檔放心下載得從A城到B城花費(fèi)最低等等的一系列問(wèn)題。二、系統(tǒng)分析設(shè)計(jì)一個(gè)交通咨詢系統(tǒng)，能咨詢從任何一個(gè)城市頂點(diǎn)到另一城市感謝閱讀頂點(diǎn)之間的最短路徑(里程)、最低花費(fèi)或是最少時(shí)間等問(wèn)題。對(duì)于不感謝閱讀同的咨詢要求，可輸入城市間的路程、所需時(shí)間或是所需費(fèi)用等信息。精品文檔放心下載針對(duì)最短路徑問(wèn)題，在本系統(tǒng)中采用圖的相關(guān)知識(shí)，以解決在實(shí)謝謝閱讀際情況中的最短路徑問(wèn)題，本系統(tǒng)中包括了建立圖的存儲(chǔ)結(jié)構(gòu)、單源精品文檔放心下載最短問(wèn)題、對(duì)任意一對(duì)頂點(diǎn)間最短路徑問(wèn)題三個(gè)問(wèn)題，這對(duì)以上幾個(gè)感謝閱讀問(wèn)題采用了迪杰斯特拉算法和弗洛伊德算法。并未本系統(tǒng)設(shè)置一人性謝謝閱讀化的系統(tǒng)提示菜單，方便使用者的使用。~三、概要設(shè)計(jì)可以將該系統(tǒng)大致分為三個(gè)部分：①建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)；②解決單源最短路徑問(wèn)題；③實(shí)現(xiàn)兩個(gè)城市頂點(diǎn)之間的最短路徑問(wèn)題。交通咨詢系統(tǒng)迪杰建立斯特圖的拉算存儲(chǔ)法（單結(jié)構(gòu)源最義短路徑）

費(fèi)洛依德算法（任意頂點(diǎn)對(duì)間最短路徑）迪杰斯特拉算法流圖：~弗洛伊德算法流圖：~~四、詳細(xì)設(shè)計(jì)4.1建立圖的存儲(chǔ)結(jié)構(gòu)定義交通圖的存儲(chǔ)結(jié)構(gòu)。鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)精品文檔放心下載系的矩陣。設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是具有感謝閱讀如下定義的n階方陣。W，若(V,V)或V,VE(G)謝謝閱讀 ij i j i jA[i,j]0或，其他情況注：一個(gè)圖的鄰接矩陣表示是唯一的！其表示需要用一個(gè)二維數(shù)組存儲(chǔ)頂點(diǎn)之間相鄰關(guān)系的鄰接矩陣并且還需要用一個(gè)具有n個(gè)元素的一維數(shù)組來(lái)存儲(chǔ)頂點(diǎn)信息（下標(biāo)為i的元素存儲(chǔ)頂點(diǎn)Vi的信息）。鄰接矩陣的存儲(chǔ)結(jié)構(gòu)：感謝閱讀#defineMVNum100//最大頂點(diǎn)數(shù)typedefstruct{VertexTypevexs[MVNum];//頂點(diǎn)數(shù)組，類型假定為char型Adjmatrixarcs[MVNum][MVNum];//鄰接矩陣，假定為int型精品文檔放心下載}MGraph;注：由于有向圖的鄰接矩陣是不對(duì)稱的，故程序運(yùn)行時(shí)只需要輸精品文檔放心下載入所有有向邊及其權(quán)值即可。~4.2單源最短路徑單源最短路徑問(wèn)題：已知有向圖(帶權(quán))，期望找出從某個(gè)源點(diǎn)S感謝閱讀∈V到G中其余各頂點(diǎn)的最短路徑。迪杰斯特拉算法即按路徑長(zhǎng)度遞增產(chǎn)生諸頂點(diǎn)的最短路徑算法。精品文檔放心下載算法思想：設(shè)有向圖G=(V,E)，其中V={1,2，……n}，cost是表謝謝閱讀示G的鄰接矩陣，cost[i][j]表示有向邊<i,j>的權(quán)。若不存在有向邊<i,j>，則精品文檔放心下載cost[i][j]的權(quán)為無(wú)窮大（這里取值為32767）。設(shè)S是一個(gè)集合，集合中一個(gè)元素表示一個(gè)頂點(diǎn)，從源點(diǎn)到這些頂點(diǎn)的最短距離已經(jīng)求出。設(shè)頂點(diǎn)V為源點(diǎn)，集合S的初態(tài)只包含頂點(diǎn)V。數(shù)組dist記錄精品文檔放心下載1 1從源點(diǎn)到其它各頂點(diǎn)當(dāng)前的最短距離，其初值為dist[i]=cost[i][j]，i=2，……n。從S之外的頂點(diǎn)集合V-S中選出一個(gè)頂點(diǎn)謝謝閱讀w，使dist[w]的值最小。于是從源點(diǎn)到達(dá)w只通過(guò)S中的頂點(diǎn)，把w加入集合S中，調(diào)整dist中記錄的從源點(diǎn)到V-S中每個(gè)頂點(diǎn)v的距離：從原來(lái)的dist[v]和dist[w]+cost[w][v]中選擇較小的值作為新的dist[v]。重復(fù)上述過(guò)程，直到S中包含V中其余頂點(diǎn)的最短路徑。精品文檔放心下載最終結(jié)果是：S記錄了從源點(diǎn)到該頂點(diǎn)存在最短路徑的頂點(diǎn)集合，數(shù)組dist記錄了從源點(diǎn)到V中其余各頂點(diǎn)之間的最短路徑，path是最短路徑的路徑數(shù)組，其中path[i]表示從源點(diǎn)到頂點(diǎn)i之間的最短路徑的前驅(qū)頂點(diǎn)。謝謝閱讀ij2i2jiji1j~4.3任意一對(duì)頂點(diǎn)之間的最短路徑任意頂點(diǎn)對(duì)之間的最短路徑問(wèn)題，是對(duì)于給定的有向網(wǎng)絡(luò)圖G=(V,E),要對(duì)G中任意一對(duì)頂點(diǎn)有序?qū)Γ癡,W(V≠W)”，找出V到W的最短路徑。而要解決這個(gè)問(wèn)題，可以依次把有向網(wǎng)絡(luò)圖中每個(gè)頂點(diǎn)作為源點(diǎn)，重復(fù)執(zhí)行前面的迪杰斯特拉算法n次，即可求得每對(duì)之間的最短路徑。精品文檔放心下載費(fèi)洛伊德算法的基本思想：假設(shè)求從V到V的最短路徑。如果感謝閱讀i j存在一條長(zhǎng)度為arcs[i][j]的路徑，該路徑不一定是最短路徑，還需要進(jìn)行n次試探。首先考慮路徑<v,v>和<v,v>是否存在。如果存謝謝閱讀i 1 1 j在，則比較路徑<v.v>和<v,v,v>的路徑長(zhǎng)度，取長(zhǎng)度較短者為當(dāng)前所求得。該路徑是中間頂點(diǎn)序號(hào)不大于1的最短路徑。其次，考慮感謝閱讀感謝閱讀i j那么<v,…,v,…,v>可分解為<v,…,v>和<v,…,v>，而這兩條路謝謝閱讀i 2 j i 2 2 j徑是前一次找到的中間點(diǎn)序號(hào)不大于1的最短路徑，將這兩條路徑長(zhǎng)度相加就得到路徑<v,…,v,…v>的長(zhǎng)度。將該長(zhǎng)度與前一次中求得謝謝閱讀i 2 j的從v到v的中間頂點(diǎn)序號(hào)不大于1的最短路徑比較，取其長(zhǎng)度較精品文檔放心下載i j短者作為當(dāng)前求得的從v到v的中間頂點(diǎn)序號(hào)不大于2的最短路徑。感謝閱讀i j依此類推……直至頂點(diǎn)v加入當(dāng)前從v到v的最短路徑后，選出從感謝閱讀n i j到v的中間頂點(diǎn)序號(hào)不大于n的最短路徑為止。由于圖G中頂點(diǎn)序感謝閱讀j號(hào)不大于n，所以v到v的中間頂點(diǎn)序號(hào)不大于n的最短路徑，已考精品文檔放心下載i j慮了所有頂點(diǎn)作為中間頂點(diǎn)的可能性，因此，它就是v到v的最短謝謝閱讀i j~路徑。五、運(yùn)行與測(cè)試測(cè)試實(shí)例1：利用如下圖所示的有向圖來(lái)測(cè)76 74664242656455測(cè)試實(shí)例2：利用下圖求交通網(wǎng)絡(luò)圖（無(wú)向圖）的最短路徑。精品文檔放心下載2553北京1704西安2695徐州8124成都5113349鄭州565115792368上海13857廣州 6實(shí)例1運(yùn)行結(jié)果：~~實(shí)例2運(yùn)行結(jié)果：~六、總結(jié)與心得該課程設(shè)計(jì)主要是從日常生活中經(jīng)常遇到的交通網(wǎng)絡(luò)問(wèn)題入手，精品文檔放心下載進(jìn)而利用計(jì)算機(jī)去建立一個(gè)交通咨詢系統(tǒng)，以處理和解決旅客們關(guān)心謝謝閱讀的各種問(wèn)題（當(dāng)然此次試驗(yàn)最終主要解決的問(wèn)題是：最短路徑問(wèn)題）。精品文檔放心下載這次試驗(yàn)中我深刻的了解到了樹(shù)在計(jì)算機(jī)中的應(yīng)用是如何的神謝謝閱讀奇與靈活，對(duì)于很多的問(wèn)題我們可以通過(guò)樹(shù)的相關(guān)知識(shí)來(lái)解決，特別感謝閱讀是在解決最短路徑問(wèn)題中，顯得尤為重要。經(jīng)過(guò)著次實(shí)驗(yàn)，我了解到了關(guān)于樹(shù)的有關(guān)算法，如：迪杰斯特拉謝謝閱讀算法、弗洛伊德算法等，對(duì)樹(shù)的學(xué)習(xí)有了一個(gè)更深的了解。精品文檔放心下載參考文獻(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>#defineMVNum100#defineMaxint32767enumboolean{FALSE,TRUE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];Adjmatrixarcs[MVNum][MVNum];精品文檔放心下載}MGraph;intD1[MVNum],p1[MVNum];intD[MVNum][MVNum],p[MVNum][MVNum];精品文檔放心下載voidCreateMGraph(MGraph*G,intn,inte)感謝閱讀{inti,j,k,w;for(i=1;i<=n;i++)G->vexs[i]=(char)i;for(i=1;i<=n;i++)for(j=1;j<=n;j++)G->arcs[i][j]=Maxint;printf("輸入%d條邊的i.j及w:\n",e);精品文檔放心下載for(k=1;k<=e;k++){scanf("%d,%d,%d",&i,&j,&w);感謝閱讀G->arcs[i][j]=w;}printf("有向圖的存儲(chǔ)結(jié)構(gòu)建立完畢！\n");精品文檔放心下載}voidDijkstra(MGraph*G,intv1,intn)精品文檔放心下載{intD2[MVNum],p2[MVNum];intv,i,w,min;enumbooleanS[MVNum];for(v=1;v<=n;v++){S[v]=FALSE;D2[v]=G->arcs[v1][v];if(D2[v]<Maxint)p2[v]=v1;else~p2[v]=0;}D2[v1]=0;S[v1]=TRUE;for(i=2;i<n;i++){min=Maxint;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){v=w;min=D2[w];}S[v]=TRUE;for(w=1;w<=n;w++)if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){感謝閱讀D2[w]=D2[v]+G->arcs[v][w];感謝閱讀p2[w]=v;}}printf("路徑長(zhǎng)度 路徑\n");for(i=1;i<=n;i++){printf("%5d",D2[i]);printf("%5d",i);v=p2[i];while(v!=0){printf("<-%d",v);v=p2[v];}printf("\n");}}voidFloyd(MGraph*G,intn)精品文檔放心下載{inti,j,k,v,w;for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(G->arcs[i][j]!=Maxint)精品文檔放心下載p[i][j]=j;elsep[i][j]=0;D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++){for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(D[i][k]+D[k][j]<D[i][j]) {謝謝閱讀~D[i][j]=D[i][k]+D[k][j];p[i][j]=p[i][k];}}}}voidmain(){MGraph*G;intm,n,e,v,w,k;intxz=1;G=(MGraph*)malloc(sizeof(MGraph));謝謝閱讀printf("輸入圖中頂點(diǎn)個(gè)數(shù)和邊數(shù)n,e:");謝謝閱讀scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);while(xz!=0){printf("************求城市之間最短路徑************\n");感謝閱讀printf("=========================================\n");printf("1.求一個(gè)城市到所有城市的最短路徑\n");printf("2.求任意的兩個(gè)城市之間的最短路徑\n");printf("=========================================\n");printf("請(qǐng)選擇: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=p[v][w];if(k==