word目錄一、概述1二、系統(tǒng)分析1三、概要設計2四、詳細設計5567五、運行與測試8參考文獻11附錄1215 / 16交通咨詢系統(tǒng)設計最短路徑問題一、概述在交通網絡日益興旺的今天，針對人們關心的各種問題，利用計算機建立一個交通咨詢系統(tǒng)。在系統(tǒng)中采用圖來構造各個城市之間的聯(lián)系，圖中頂點表示城市，邊表示各個城市之間的交通關系，所帶權值為兩個城市間的消耗。這個交通咨詢系統(tǒng)可以回答旅客提出的各種問題，例如：如何選擇一條路徑使得從A城到B城途中中轉次數最少；如何選擇一條路徑使得從A城到B城里程最短；如何選擇一條路徑使得從A城到B城花費最低等等的一系列問題。二、系統(tǒng)分析設計一個交通咨詢系統(tǒng)，能咨詢從任何一個城市頂點到另一城市頂點之間的最短路徑(里程)、最低花費或是最少時間等問題。對于不同的咨詢要求，可輸入城市間的路程、所需時間或是所需費用等信息。針對最短路徑問題，在本系統(tǒng)中采用圖的相關知識，以解決在實際情況中的最短路徑問題，本系統(tǒng)中包括了建立圖的存儲結構、單源最短問題、對任意一對頂點間最短路徑問題三個問題，這對以上幾個問題采用了迪杰斯特拉算法和弗洛伊德算法。并未本系統(tǒng)設置一人性化的系統(tǒng)提示菜單，方便使用者的使用。三、概要設計可以將該系統(tǒng)大致分為三個局部： 建立交通網絡圖的存儲結構； 解決單源最短路徑問題； 實現兩個城市頂點之間的最短路徑問題。交通咨詢系統(tǒng)迪杰斯特拉算法單源最短路徑費洛依德算法任意頂點對間最短路徑建立圖的存儲結構義迪杰斯特拉算法流圖：弗洛伊德算法流圖：四、詳細設計建立圖的存儲結構定義交通圖的存儲結構。鄰接矩陣是表示圖形中頂點之間相鄰關系的矩陣。設G=(V,E)是具有n個頂點的圖，如此G的鄰接矩陣是具有如下定義的n階方陣。注：一個圖的鄰接矩陣表示是唯一的！其表示需要用一個二維數組存儲頂點之間相鄰關系的鄰接矩陣并且還需要用一個具有n個元素的一維數組來存儲頂點信息下標為i的元素存儲頂點的信息。鄰接矩陣的存儲結構：#define MVNum 100 /最大頂點數typedef struct VertexType vexsMVNum;/頂點數組，類型假定為char型 Adjmatrix arcsMVNumMVNum;/鄰接矩陣，假定為int型MGraph;注：由于有向圖的鄰接矩陣是不對稱的，故程序運行時只需要輸入所有有向邊與其權值即可。單源最短路徑單源最短路徑問題：有向圖(帶權)，期望找出從某個源點SV到G中其余各頂點的最短路徑。迪杰斯特拉算法即按路徑長度遞增產生諸頂點的最短路徑算法。算法思想：設有向圖G=(V,E)，其中V=1,2，n，cost是表示G的鄰接矩陣，costij表示有向邊<i,j>的權。假如不存在有向邊<i,j>，如此costij 的權為無窮大這里取值為32767。設S是一個集合，集合中一個元素表示一個頂點，從源點到這些頂點的最短距離已經求出。設頂點V1為源點，集合S的初態(tài)只包含頂點V1。數組dist記錄從源點到其它各頂點當前的最短距離，其初值為disti= costij，i=2，n。從S之外的頂點集合V-S中選出一個頂點w，使distw 的值最小。于是從源點到達w只通過S中的頂點，把w參加集合S中，調整dist中記錄的從源點到V-S中每個頂點v的距離：從原來的distv和distw+costwv中選擇較小的值作為新的distv。重復上述過程，直到S中包含V中其余頂點的最短路徑。 最終結果是：S記錄了從源點到該頂點存在最短路徑的頂點集合，數組dist記錄了從源點到V中其余各頂點之間的最短路徑，path是最短路徑的路徑數組，其中pathi表示從源點到頂點i之間的最短路徑的前驅頂點。 任意一對頂點之間的最短路徑任意頂點對之間的最短路徑問題，是對于給定的有向網絡圖G=(V,E),要對G中任意一對頂點有序對，“V,W(VW)，找出V到W的最短路徑。而要解決這個問題，可以依次把有向網絡圖中每個頂點作為源點，重復執(zhí)行前面的迪杰斯特拉算法n次，即可求得每對之間的最短路徑。 費洛伊德算法的根本思想：假設求從Vi到Vj的最短路徑。如果存在一條長度為arcsij的路徑，該路徑不一定是最短路徑，還需要進展n次試探。首先考慮路徑<vi,v1>和<v1,vj>是否存在。如果存在，如此比擬路徑<vi.vj>和<vi,v1,vj>的路徑長度，取長度較短者為當前所求得。該路徑是中間頂點序號不大于1的最短路徑。其次，考慮從vi到vj是否包含有頂點v2為中間頂點的路徑< vi,v2,vj>，假如沒有，如此說明從vi到vj的當前最短路徑就是前一步求出的；假如有，那么<vi,v2,vj>可分解為<vi,v2>和<v2,vj>，而這兩條路徑是前一次找到的中間點序號不大于1的最短路徑，將這兩條路徑長度相加就得到路徑<vi,v2,vj>的長度。將該長度與前一次中求得的從vi到vj的中間頂點序號不大于1的最短路徑比擬，取其長度較短者作為當前求得的從vi到vj的中間頂點序號不大于2的最短路徑。依此類推直至頂點vn參加當前從vi到vj的最短路徑后，選出從vi到vj的中間頂點序號不大于n的最短路徑為止。由于圖G中頂點序號不大于n，所以vi到vj的中間頂點序號不大于n的最短路徑，已考慮了所有頂點作為中間頂點的可能性，因此，它就是vi到vj的最短路徑。五、運行與測試3測試實例1：利用如如下圖所示的有向圖來測試13177161747632646456262455測試實例2：利用如下圖求交通網絡圖無向圖的最短路徑。2553某某70416952349某某某某51181234某某515796512368某某13857某某6實例1運行結果：實例2運行結果：六、總結與心得該課程設計主要是從日常生活中經常遇到的交通網絡問題入手，進而利用計算機去建立一個交通咨詢系統(tǒng)，以處理和解決旅客們關心的各種問題當然此次試驗最終主要解決的問題是：最短路徑問題。這次試驗中我深刻的了解到了樹在計算機中的應用是如何的神奇與靈活，對于很多的問題我們可以通過樹的相關知識來解決，特別是在解決最短路徑問題中，顯得尤為重要。經過著次實驗，我了解到了關于樹的有關算法，如：迪杰斯特拉算法、弗洛伊德算法等，對樹的學習有了一個更深的了解。參考文獻【1】數據結構嚴蔚敏.清華大學.【2】數據結構課程設計蘇仕華.極械工業(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("有向圖的存儲結構建立完畢！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("輸入圖中頂點個數和邊數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("輸入源點或起點和終點:v,w:");scanf("%d,%d",&v,&w);k=pvw;if (k=0)printf("頂點%d 到 %d 無路徑!n",v,w);elseprintf("從頂點%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("求單源路徑，輸入源點v:");scanf("%d",&v);Dijkstra(G,v,n);printf("完畢求最短路徑，再見!n");