信息科学与工程学院课程设计任务书题目：交通咨询系统设计学号： 201112220141姓名：年级：专业：计算机应用与技术课程：数据结构指导教师：职称：完成时间：课程设计任务书及成绩评定一、需求分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。

对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。

本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。

1.1.1建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。

图的邻接矩阵是定义如下的n 阶方阵：设G=（V ，E ）是一个图，结点集为{}n v v v V ,,,21 =。

G 的邻接矩阵,E,,0E,,)(,)(⎪⎩⎪⎨⎧>∉<∞>∈<==⨯⨯j i j i j i j i n n j i ij n n ij v v v v v v v v w a a A ）或当（，或）或当（， 当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。

图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n 个元素的一维数组来存储顶点信息，其中下标为i 的元素存储顶点i 的信息。

因此，图的邻接矩阵的存储结构定义如下：1.1.2 单源最短路径最短路径的提法很多。

在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点S ∈V 到G 中其余各顶点的最短路径。

为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。

那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra ）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。

迪杰斯特拉算法求最短路径的实现思想是：设G=（V ，E ）是一个有向图，结点集为，}v ,,v ,{v V n 21⋯=，cost 是表示G 的邻接矩阵，cost[i][j]表示有向边<i,j>的权。

若不存在有向边<i,j>，则cost[i][j]的权为无穷大（这里取值为32767）。

设S 是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。

设顶点v 1为源点，集合S 的初态只包含一个元素，即顶点v 1。

数组dist 记录从源点到其他顶点当前的最短距离，其初值为dist[i]=cost[v 1][i],i=1,2,……,n 。

从S 之外的顶点集合V-S 中选出一个顶点w ，使dist[w]的值最小。

于是从源点到达w 只通过S 中顶点，把w 加入集合S 中，调整dist 中记录的从源点到V-S 中每个顶点v 的距离：从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。

重复上述过程，直到V-S 为空。

最终结果是：S 记录了从源点到该顶点存在最短路径的顶点集合，数组dist 记录了源点到V 中其余各顶点之间的最短路径，path 是最短路径的路径数组，其中path[i]表示从源点到顶点i 之间的最短路径的前驱顶点。

因此，迪杰斯特拉算法可用自然语言描述如下：1.1.3 任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V ，E ），要对G 中任意一对顶点有序对“v,w(v ≠w)”,找出v 到w 的最短路径。

要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n 次，即可以求得每对顶点之间的最短路径。

这里还可以用另外一种方法，称作费洛伊德（Floyd ）算法。

费洛伊德（Floyd ）算法算法的基本思想是：假设求从顶点 v i 到v j 的最短路径。

如果从vi 到vj存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，还需要进行n次试探。

首先考虑路径<vi ,v1>和<v1,vj>是否存在。

如果存在，则比较<vi ,vj>和< vi,v1,vj>的路径长度，取长度较短者为当前所求得的最短路径。

该路径是中间顶点序号不大于1的最短路径。

其次，考虑从vi 到vj是否包含有顶点v2为中间顶点的路径<vi,…,v2,…,vj>，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么<vi ,…,v2,…,vj>可分解为<vi, (v)2>和<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的最短路径。

1.2 程序流程图二、详细设计2.1 建立有向图的存储结构void CreateMGraph(MGraph * G,int n,int e) {int i,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("有向图建立完毕\n");}2.2迪杰斯特拉算法void Dijkstra(MGraph *G,int v1,int n) {int D2[MVNum],P2[MVNum];int v,i,w,min;enum boolean S[MVNum];for(v=1;v<=n;v++){S[v]=FALSE;D2[v]=G->arcs[v1][v];if(D2[v]<Maxint)P2[v]=v1;elseP2[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("路径长度路径\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");}}2.3 费洛伊德算法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->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];;}}}}2.4 运行主控程序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("1.求一个城市到所有城市的最短路径\n");printf(“2.求任意的两个城市之间的最短路径\n");printf(" 请选择：1 或 2,选择 0 退出:");scanf("%d",&xz);if(xz==2){Floyd(G,n);printf("输入起点和终点:v,w:");scanf("%d,%d",&v,&w);k=P[v][w];if(k==0)printf("顶点 %d 到 %d 无路径!\n",v,w);else{ printf("从顶点%d到%d的最短路径是::%d",v,w,v);while(k!=w){printf("→¨²%d",k);k=P[k][w];}printf("→¨²%d",w);printf("路径长度:%d\n",D[v][w]);}}else if(xz==1){printf("求单源路径，输入源点 v :");scanf("%d",&v);Dijkstra(G,v,n);}}printf("结束求最短路径");}三、调试分析编译: 在第一次编译时出现了很多错误，是因为我对C语言的不熟练，比如调用费洛伊德算法时出现了调用的错误，找了好久，才改正过来，还有就是for 语句的运用，由于本次程序要用很多for循环，我把一次for循环放到了上面for循环中，导致程序不能正确输出结果。