目录1 概述 (2)1.1 问题描述 (2)1.2 实现意义 (2)2 系统分析 (2)2.1 需求分析 (2)2.1.1程序的功能 (2)2.1.2输入输出的要求 (2)2.2 设计思想 (2)2.3 设计要求 (3)3 概要设计 (3)3.1用邻接矩阵建立交通网络模块 (3)3.2 查询任意两个顶点之间的最短路径 (4)3.3 查询一个城市到其他所有城市的最短路径 (5)4 详细设计 (5)4.1 用邻接矩阵构造图结构函数CreateMGraph() (5)4.2 费洛伊德Floyd() (6)4.3 迪杰斯特拉Dijkstra() (6)4.4 主要函数流程图及其函数调用 (7)4.4.1 主要函数流程图 (7)4.4.2 一个城市到其他城市的路径调用 (8)4.4.3 任意两个城市之间路径调用 (8)5 运行与测试 (8)5.1 有向图存储结构的建立模块的输出 (9)5.2 单源路径迪杰斯特拉算法模块的输出 (10)5.3 费洛伊德算法模块的输出 (10)6 总结与心得 (10)参考文献 (11)附录 (11)1 概述1.1 问题描述在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和所需时间等问题也感兴趣。

对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。

图中顶点表示城市之间的交通关系。

这个交通系统可以回答旅客提出的各种问题。

比如任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。

1.2 实现意义便于人们的日常出行，且更好地满足了用户的出行需求。

这种最短路径问题的计算方法既简单又便于实现，同时大大提高了计算机的运行速率。

2 系统分析2.1 需求分析2.1.1程序的功能（1）用户自己可以建立不同的路径之间的关系网（2）可以查询某个城市到达其余各城市的最短路径。

（3）可以任一查询两个城市之间的最短路径。

2.1.2输入输出的要求在刚进入主界面后系统提示输入建立交通网络储存结构，输入顶点个数和和边数为整数不能输入其他字符，随后系统提示输入边与边之间的关系分别为i，j，w表示边之间的距离。

然后进入查询页面，输入整数1，2，0分别表示你所要查询的功能：一个城市至其他所有城市的最短路径查询、任意两个城市之间的最短路径查询、退出程序。

不能输入其他字符否则不能执行操作。

在整个操作都是用整数表示城市。

2.2 设计思想用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现交通咨询系统设计的问题。

2.3 设计要求该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的最短路径问题。

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

3 概要设计3.1用邻接矩阵建立交通网络模块\3-2-1 建立邻接矩阵注：用户构建交通网络时，输入顶点个数n，边数e。

然后在分别输入每个顶点i和j之间的距离w。

程序将自动根本用户所输入的构建邻接矩阵。

3.2 查询任意两个顶点之间的最短路径3-2-2 费洛伊德算法注：用户输入他所需要查询的城市的起点v和终点w，程序利用费洛伊德算法依次输出起点v到终点w所经过的顶点。

3.3 查询一个城市到其他所有城市的最短路径3-2-3 迪杰斯特拉算法注：用户输入他所需要查询的城市的起点v，程序将会调用迪杰斯特拉算法，用S保存经过的顶点，最终会输出用户所需要查询的顶点v到其他所有顶点的最短路径。

4 详细设计4.1 用邻接矩阵构造图结构函数CreateMGraph()其中vexs[MVNum]保存顶点信息，arcs[MVNum][MVNum]用于保存边与边之间的信息。

在构建时通过输入的边数i，j作为矩阵的行、列确定顶点的出度和入度。

用邻接矩阵方法存储图，很容易确定图的任意两个顶点是否是有边相连，因此用邻接矩阵对有利于后面费洛伊德算法和迪杰斯特拉算法。

数据类型定义：typedef struct{VertexType vexs[MVNum];Adjmatrix arcs[MVNum][MVNum];}MGraph;邻接矩阵的程序代码：for(k=1;k<=e;k++) //读入e条边建立邻接矩阵{ printf(" 第%d条边的信息:",k);scanf("%d,%d,%d",&i,&j,&w);G->arcs[i][j]=w;G->arcs[j][i]=w;}4.2 费洛伊德Floyd()费洛伊德算法对求任意两个顶点之间的路径较优。

用邻接矩阵保存图存储后，另外需要存一个二维数组A存放当前顶点之间的最短路径长度。

分量A[i][j]表示当前顶点i到j的最短路径长度。

费洛伊德算法的基本思维是递推产生一个矩阵序列A0，A1，A2，….Ak，…An，其中Ak[i][j]表示从顶点到vi到顶点vj 的路径上所经过的顶点编号不大于k的最短路径长度。

A[i][j]=cost[i][j]A(k+1)[i][j]=min{Ak[i][j],Ak[i+1][k+1]+Ak[k+1][j]}费洛伊德主要算法，若Ak[i][j]已求出，顶点i到顶点k+1的路径长度为Ak[i][k+1]，顶点路径长度为Ak[i][j]，顶点k+1到顶点j的路径长度为Ak[k+1][j]，如果此时Ak[i][k+1]+Ak[k+1][j]< Ak[i][j],则将原来的顶点i到顶点j的路径改为顶点，否则不需要修改顶点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];}}}4.3 迪杰斯特拉Dijkstra()迪杰斯特拉算法对求一个顶到到其他所有顶点的路径较优。

初始时，S中只包含原点，顶点v到自己的距离为0，D中包含出v外的其他顶点，v到D中顶点u的距离为边上的权值。

从D中选取一个顶点k，顶点v到顶点k的距离最小，然后把顶点k加入到S中，该选定的距离就是v到k的最短路径长度。

以顶点k为新考虑的中间点，修改顶点v到U中各顶点的距离，若从原点v到顶点u的距离比原来的距离（不经过k）的距离看，短，则修改顶点u的距离值，修改后的距离值为顶点v到顶点k的距离加上边<k,u>上的权。

迪杰斯特拉的算法：D2[v1]=0;S[v1]=1; //原点编号放入s中for(i=2;i<n;i++){ min=IDF;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){v=w;min=D2[w];}S[v]=1; //修改顶点u放入s中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;}}4.4 主要函数流程图及其函数调用4.4.1 主要函数流程图4.4.2 一个城市到其他城市的路径调用4-5-2 调用dijkstra()4.4.3 任意两个城市之间路径调用4-5-3 调用floyd()5 运行与测试求有向图的最短路径：如图5 所示的有向图，求顶点a到其余顶点的最短路径；分别求顶点b到顶点d之间以及顶点a到顶点d的最短路径。

图5 一个有向图因为在算法中，为了操作简便，对于图的顶点都是用序号来表示的，所以顶点的字母就用其对应的序号来操作：a(1)、b(2)、c(3)、d(4)、e(5)、f(6)、g(7)。

5.1 有向图存储结构的建立模块的输出a db cegf5.2 单源路径迪杰斯特拉算法模块的输出5.3 费洛伊德算法模块的输出6 总结与心得在这次课设中，我学到很多。

通过这次课设不仅知道了如何用狄克斯特拉和费洛伊德这两种算法求最短路径，最重要的是通过这次课设我知道自己在c语言、数据结构上存在的不足之处，引起了我的重视。

以前总是依赖于书，在学算法时总，觉得了解了这个算法的基本功能就可以了，其实没有掌握类似于费洛伊德这些算法的运用，如何建立数组保存，如何输出等。

在写程序中我也遇到了许多错误，开始思维一直局限在该如何保存输入的信息以便于在费洛伊德算法中运用。

后来通过不断的修改程序定义数组保存顶点的点数和边数，建立邻接矩阵构成无向图。

在考虑求最短路径算法时，发现迪杰斯特拉和弗洛伊德各有各的优点，最后决定用迪杰斯特拉算法求一个城市到其他城市的最短路径算法，费洛伊德算任意两点之间的最短路径。

当然如果完全按照书上的程序去写的话仍然会很多的不足，所以在程序稍稍修改过后就可以正确运行了。

深知我们现在书上学的都只是皮毛，对以后真正从事开发研究的工作而言我们懂的实在是太少了，在以后的日子里我会好好学习C语言和数据结构。

程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。

在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C语言，C++具有的语句简洁，使用灵活，执行效率高等特点。

参考文献[1] 数据结构课程设计苏仕华等编著机械工业出版社[2] 数据结构（C语言版）严蔚敏吴伟民编著清华大学出版社[3] C程序设计（第三版）谭浩强著清华大学出版社附录#include<stdio.h>#include<stdlib.h>#define MVNum 100 //最大顶点数#define Maxint 32767enum boolean{FALSE,TRUE};typedef char Vertextype;typedef int Adjmatrix;typedef struct{Vertextype vexs[MVNum]; //顶点数组类型假定为char型Adjmatrix arcs[MVNum] [MVNum]; // 邻接矩阵假定为int型}MGraph;int D1[MVNum], p1[MVNum];int D[MVNum][MVNum],p[MVNum][MVNum];//文件名save.cvoid CreateMGraph(MGraph *G,int n,int e){ //采用邻接矩阵表示法构造有向图G,n,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++){ //读入e条边,建立邻接矩阵scanf("%d,%d,%d",&i,&j,&w);G->arcs[i][j]=w;}printf ("有向图的存储结构建立完毕\n");}//文件名:dijkstra.c(迪杰斯特拉算法void Dijkstra(MGraph *G, int v1,int n){ //用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径p[v]及其权D[v] //设G是有向图的邻接矩阵若边<i,j>不存在则G[i][j]=Maxint//S[v]为真当且仅当v属于S及以求的从v1到v的最短路径int D2[MVNum], p2[MVNum];int v,i,w,min;enum boolean S[MVNum];for(v=1;v<=n;v++){ // 初始化S和DS[v]=FALSE; //置空最短路径终点集D2[v]=G->arcs[v1][v]; //置初始的最短路径值if(D2[v]< Maxint)p2[v]=v1; //v1是的前趋双亲elsep2[v]=0; //v 无前趋} // End_forD2[v1]=0;S[v1]=TRUE; //S集初始时只有源点源点到源点的距离为0//开始循环每次求的V1到某个V顶点的最短路径并加V到S集中 for(i=2;i<n;i++){ //其余n-1个顶点for(i=2;i<n;i++)min=Maxint; // 当前所知离v1顶点的最近距离设初值为∞for(w=1;w<=n;w++) //对所有顶点检查if(!S[w] && D2[w]<min){ //找离v1最近的顶点w并将其赋给v距离赋给minv=w; //在S集之外的离v1最近的顶点序号min=D2[w]; //最近的距离} //W顶点距离V1顶点更近S[v]=TRUE; //将v并入S集for(w=1;w<=n;w++) //更新当前最短路径及距离if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){ //修改D2[w]和p2[w]w 属于V-SD2[w]=D2[v]+G->arcs[v][w]; //更新D2[w]p2[w]=v;} //End_if} //End_forprintf ("路径长度路径\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");}}//文件名floyd.c(费洛伊德算法void Floyd(MGraph *G, int n){int i, j, k;for(i=1;i<=n;i++) //设置路径长度D和路径path初值for(j=1;j<=n;j++){if(G->arcs[i][j]!=Maxint)p[i][j]=j; //j是i的后继elsep[i][j]=0;D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++) {{ //做K次迭代每次均试图将顶点K扩充到当前求得的从i到j的最短路径pij 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];}}}}}void main(){MGraph * G;int 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 退出:");scanf("%d",&xz);if(xz==2){Floyd(G,n); //调用费洛伊德算法printf("输入起点和终点: v,w:");scanf("%d,%d",&v,&w );k=p[v][w]; //k为起点v的后继顶点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); // 输出终点wprintf(" 路径长度:%d\n",D[v][w]);}if(xz==1){printf("求单源路径输入起点v :");scanf("%d", &v);Dijkstra(G,v,n); //调用迪杰斯特拉算法}}printf("结束求最短路径再见\n");}。