交通咨询系统设计

编号 学时数 实验五 3课时 实验项目名称 指导教师 冯韵 班级 成 绩 交通咨询系统设计 计科一班 学号 33 姓名 周兴 实验日期 2010-10-16 一、实验目的:设计一个交通咨询系统能让旅客咨询从任意一个城市顶点到另一城市顶点之间的最短路径或最低花费或最少时间等问题。 二、内容与设计思想：（设计思想、主要数据结构、主要代码结构、主要代码段分析） 1.设计思想:一是用有向图的邻接矩阵建立交通网络图的存储结构；二是是用迪杰斯特拉（Dijkstra）算法解决源点到所有点的最短路径问题；三是用费罗伊德（Floyd）算法算出任意两点之间的最短路径。

2.主要数据结构：1.建立有向图的存储结构 2.迪杰斯特拉算法 3.费罗伊德算法 4.主框架函数的实现 3.主要代码结构：

{//采用邻接矩阵表示法构造有向图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\ for(k=1;k<=e;k++){

scanf(\"%d,%d,%d\ G->arcs[i][j]=w; }

printf(\"有向图的存储结构建立完毕！\\n\"); }

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]P2[v]=0;} D2[v1]=0;S[v1]=TRUE; for(i=2;ifor(w=1;w<=n;w++)

if(!S[w]&&D2[w]{v=w;min=D2[w];} S[v]=TRUE;

for(w=1;w<=n;w++)

if(!S[w]&&(D2[v]+G->arcs[v][w]arcs[v][w]; P2[w]=v;} }

printf(\"路径长度 路径\\n\"); for(i=1;i<=n;i++){

printf(\"%5d\ printf(\"%5d\ while(v!=0){

printf(\"<-%d\ v=P2[v];} printf(\"\\n\");} }

void Floyd(MGraph*G,int n) { int i,j,k,v,w; for(i=i;i<=n;i++) for(j=1;j<=n;j++) {

if(G->arcs[i][j]!=Maxint) P[i][j]; else

P[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]void main() { MGraph*G;

int n,e,v,w,k; int xz=1;

G=(MGraph*)malloc(sizeof(MGraph)); printf(\"输入图中顶点个数和边数n,e:\"); scanf(\"%d,%d\ 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\

}

printf(\"结束求最短路径，再见！\\n\"); }

三、调试过程（测试数据设计与测试结果分析）

if(xz==2){

Floyd(G,n);

printf(\"输入源点(或称起点)和终点：v,w:\"); scanf(\"%d,%d\ k=P[v][w]; if(k==0)

printf(\"顶点%d到%d无路径!\\n\ else

{ printf(\"从顶点%d到%d的最短路径是：%d\ while(k!=w){

printf(\"→%d\ k=P[k][w]; } printf(\"→%d\

printf(\" 路径长度：%d\\n\ } else

if(xz==1){

printf(\"求单源路径，输入源点v：\");

scanf(\"%d\ Dijkstra(G,v,n); }

按要求输入图中的定点个数和边数n,e:4,5

i,j是图中边的顶点编号，w是边的权值

按要求输入:

按enter键选择1，求单源路径，输入1（求顶点1

到其它点的最短路径）

此为源点1到其它点的最短路径

然后选择2后，程序调用Floyd算法 输入源点和终点v，w：2,3

顶点2到顶点3无路径，选择0退出。

四、总结

1、设计中遇到的问题及解决过程

在输入i,j,w的值时对数据的输入规则不够清楚，有向图的认识不熟悉，多看几遍实验程序了解输入数据的有向单一性。 2、设计中产生的错误及原因分析

在Floyd算法中v，w是无效引用的局部变量，将i=1错输为i=i让程序在求最短路径是发生错误

3、设计体会和收获

对于图的认识更深入了解，了解迪杰斯特拉算法和费罗伊德算法的数据结构。 五、评阅意见：