数据结构与算法课程设计-求解最短路径

综合实验任务书姓名学号班级课程名称数据结构与算法课程性质专业必修课设计时间2008年12月15日——2009年1月2日设计名称求解最短路径设计要求能够完成以下功能：1)建立图2)实现Dijkstra单源点最短路径算法3)实现Floyd算法，实现求解每对结点之间的最短路径问题4)有错误提示功能，例如非法输入时，会有报错。设计思路与设计过程根据系统功能要求，可以将问题解决分为以下步骤：（1）分析问题实质；（2）抽取问题实质，进行抽象；（3）确定数据结构；（4）选择合适的算法，进行算法设计；（5）完成系统的应用模块；（6）功能调试；（7）修改不完善的功能，增强程序健壮性；（8）根据实际添加所需功能；计划与进度由简单到复杂，争取15天左右完成任课教师意见说明

设计名称：求解最短路径 日期：2009年1月2日设计内容：设计一个系统，实现以下功能：1：建立图2：实现Dijkstra单源点最短路径算法3：实现Floyd算法，实现求解每对结点之间的最短路径问题4：退出系统设计目的与要求：（1）达到理论与实际应用相结合，能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。（2）在实践中认识为什么要学习数据结构，掌握数据结构、程序设计语言程序设计技术、之间的关系。通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计环境或器材、原理与说明：MicrosoftVisualC++6.0设计过程（步骤）或程序代码：#include<stdio.h>#include<iostream.h>#defineMAX10000#defineMAXLEN20#defineMAX_VERTEX_NUM20typedefstruct{ charvexs[MAX_VERTEX_NUM];//顶点表 intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 intvexnum,arcnum;//图的顶点数和弧数}MGRAPH;MGRAPHcreate_mgraph()//建立有向图的邻接矩阵结构{inti,j,k,h; MGRAPHmg; printf("\n\n输入顶点数和边数(用逗号隔开):"); while(1)//判断输入是否合法 { if(scanf("%d,%d",&i,&j)==2&&getchar()=='\n'&&i<MAX_VERTEX_NUM&&j<MAX_VERTEX_NUM)break; else { while(getchar()!='\n'); cout<<"输入不合法！"<<endl; printf("请重新输入顶点数和边数(用逗号隔开):"); } } mg.vexnum=i;//存放顶点数在mg.vexnum中 mg.arcnum=j;//存放边点数在mg.arcnum中 fflush(stdin);//清空缓冲区 for(i=0;i<mg.vexnum;i++) { printf("输入顶点%d的值:",i+1);//输入顶点的值 while(1)//判断选择是否合法 { if(scanf("%d",&mg.vexs[i])==1&&getchar()=='\n')break; else { while(getchar()!='\n'); cout<<"输入不合法！"<<endl; printf("请重新输入顶点%d的值:",i+1); } }fflush(stdin); }for(i=0;i<mg.vexnum;i++)//邻接矩阵初始化 for(j=0;j<mg.vexnum;j++) mg.arcs[i][j]=MAX; for(k=1;k<=mg.arcnum;k++) { printf("输入第%d条边的起始顶点和终止顶点(用逗号隔开):",k); while(1)//输入弧的起始顶点和终止顶点，并判断输入是否合法 { /* scanf("%d,%d",&i,&j)的作用：判断是否成功输入 如果i和j都被成功读入，那么scanf的返回值就是2 如果只有i被成功读入，返回值为1 如果i和j都未被成功读入，返回值为0 */ if(scanf("%d,%d",&i,&j)==2&&getchar()=='\n'&&i>0&&i<=mg.vexnum&&j>0&&j<=mg.vexnum)break; else { while(getchar()!='\n'); cout<<"输入不合法！"<<endl; printf("请重新输入起始顶点和终止顶点(用逗号隔开):"); } }fflush(stdin);while(i<1||i>mg.vexnum||j<1||j>mg.vexnum) { printf("输入错，重新输入:"); scanf("%d,%d",&i,&j); } printf("输入此边权值:");//输入弧上之权值 while(1)//判断输入是否合法 { if(scanf("%d",&h)==1&&getchar()=='\n')break; else { while(getchar()!='\n'); cout<<"输入不合法！"<<endl; printf("请重新输入此边权值:"); } }mg.arcs[i-1][j-1]=h; } returnmg;}voidDijkstra(MGRAPHmg){intcost[MAXLEN][MAXLEN];intpath[MAXLEN],flag[MAXLEN];intdist[MAXLEN];inti,j,n,v0,min,u,back=0; printf("\n求有向图单源点最短路径\n"); printf("\n\n起始顶点为:");//有向图中顶点的编号从1编起 while(1)//判断选择是否合法 { if(scanf("%d",&v0)==1&&getchar()=='\n'&&v0<=mg.vexnum)break; else { while(getchar()!='\n'); cout<<"输入不合法！"<<endl; printf("请重新输入起始点："); } }printf("\n\n");v0--;n=mg.vexnum;for(i=0;i<n;i++)//cost矩阵初始化 { for(j=0;j<n;j++)cost[i][j]=mg.arcs[i][j];cost[i][i]=0; }for(i=0;i<n;i++) { dist[i]=cost[v0][i];//dist数组初始化if(dist[i]<MAX&&dist[i]>0)//path数组初始化path[i]=v0; }for(i=0;i<n;i++)//s数组初始化 flag[i]=0; flag[v0]=1;for(i=0;i<n;i++)//按最短路径递增算法计算{ min=MAX;u=v0;for(j=0;j<n;j++) if(flag[j]==0&&dist[j]<min) { min=dist[j];u=j; }flag[u]=1;//u顶点是求得最短路径的顶点编号for(j=0;j<n;j++) if(flag[j]==0&&dist[u]+cost[u][j]<dist[j])//调整dist { dist[j]=dist[u]+cost[u][j];path[j]=u; }//path记录了路径经过的顶点 } printf("最短路径\t\t\t\t\t路径值\n");for(i=0;i<n;i++)//打印结果if(flag[i]==1) //有路径 { back=0; u=i;while(u!=v0) { printf("v%d<-",u+1);u=path[u]; back++; } printf("v%d",u+1); for(intc=46;c>0;c--) printf(""); for(;back>0;back--)//调整输出格式 printf("\b\b\b\b");printf("d=%d\n",dist[i]);} elseprintf("v%d<-v%d\t\t\t\t\t\td=MAX\n",i+1,v0+1);//无路径printf("\n\n");} voidFloyd(MGRAPHmg)//求每对结点之间的最短路径{intCost[MAXLEN][MAXLEN];//输入所求结点图的邻接矩阵intWeight[MAXLEN][MAXLEN];//结点之间的最短路径矩阵intPath[MAXLEN][MAXLEN][MAXLEN]={0};//存放结点对之间的路径，初值均为0inti,j,k,n,back=0; n=mg.vexnum; for(i=0;i<n;i++)//cost矩阵初始化 { for(j=0;j<n;j++)Cost[i][j]=mg.arcs[i][j];Cost[i][i]=0; }for(i=0;i<n;i++) {for(j=0;j<n;j++) {Weight[i][j]=Cost[i][j];//将Cost[i][j]复制到Weight[i][j]}}for(k=0;k<n;k++)//对最高下标为k的结点的路径 {for(i=0;i<n;i++)//对于所有可能的结点对 {for(j=0;j<n;j++) {if(Weight[i][j]>(Weight[i][k]+Weight[k][j])) {Weight[i][j]=Weight[i][k]+Weight[k][j];Path[i][j][k]=k;//将k结点加入到结点对（i，j）的最短路径中 } }}}printf("有向图的成本邻接矩阵\n"); printf("");for(i=0;i<=n;i++)//输出所求结点图的邻接矩阵 {if(i) {printf("v%-6d",i);//打印矩阵的行标v1,v2,……，vn}for(j=0;j<n;j++) {if(!i) {printf("v%-6d",j+1);//打印矩阵的列标 }else{ printf("%-7d",Cost[i-1][j]); }}printf("\n");} printf("\n\n\n");printf("结点对\t\t每对结点之间的最短路径\t\t\t最短路径值\n");for(i=0;i<n;i++)//输出经算法产生的结点间的最短路径矩阵 {for(j=0;j<n;j++) {printf("v%dv%d",i+1,j+1);//打印结点对printf("\t\tv%d->",i+1);//打印每对结点之间的最短路径for(k=0;k<n;k++) {if(Path[i][j][k])//打印出已存入的路径 {printf("v%d->",Path[i][j][k]+1); back++; } }printf("v%d",j+1); for(;back>0;back--)//调整输出格式 printf("\b\b\b\b"); printf("\t\t\t\t\t");printf("%d\n\n",Weight[i][j]);//打印最短路径值}}}voidoperatemenu()//操作界面{ cout<<endl; cout<<"************************************"<<endl; cout<<"1:Dijkstra"<<endl; cout<<"2:Floyd"<<endl; cout<<"3:重新建图"<<endl; cout<<"4:退出"<<endl; cout<<"************************************"<<endl;}voidmain(){ MGRAPHmg; cout<<"欢迎使用本系统！"<<endl; mg=create_mgraph();//建立有向图的邻接矩阵结构 intchoose,leave=1; while(leave) { operatemenu(); printf("请选择您需要的操作："); while(1)//判断选择是否合法 { if(scanf("%d",&choose)==1&&getchar()=='\n'&&choose>0&&choose<5)break; else { while(getchar()!='\n'); cout<<"请不要随便乱点！"<<endl; printf("请选择您需要的操作："); } } printf("\n\n"); switch(choose) { case1:Dijkstra(mg);break; case2:Floyd(mg);break; case3:mg=create_mgraph();break; case4:leave=0;break; default:cout<<"ERROR"<<endl; } } cout<<"欢迎再次使用本操作系统！"<<endl; cout<<"";}设计结果与分析：一：最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。问题解法边上权值非负情形的单源最短路径问题—Dijkstra算法所有顶点之间的最短路径—Floyd算法1：Dijkstra算法：按路径长度递增次序产生最短路径：把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的最短路径长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度————————具体步骤：初使时令S={V0},T={其余顶点}，T中顶点对应的距离值若存在<V0,Vi>，为<V0,Vi>弧上的权值若不存在<V0,Vi>，为µ从T中选取一个其距离值为最小的顶点W，加入S对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值重复上述步骤，直到S中包含所有顶点，即S=V为止——————————参数说明：Cost：为两个节点间的路径长，当没有路径时为无穷大，当i=j时为0。Dist：为路径长。Path：为路径。Flag：指示是否为最短路径经过点。back：调整输出格式的退格记录时间复杂度为O(n^2);2：Floyd算法：每对结点之间的最短路径问题是求满足下述条件的矩阵A，要求A中的任何元素A（i，j）是代表结点i到结点j的最短路径的长度。考察G中一条由i到j的最路径，i≠j。这条路径由i出发，通过一些中间结点，在j处结束。如果k是这条最短路径上的一个中间结点，那么由i到k和由k到j的这两条子路径应分别是由i到k和由k到j的最短路径。否则，这条由i到j的路径就不是具有最小长度的路径。于是，最优性原理成立。如果k是编号最高的中间结点，那么由i到k的这条最短路径上就不会有比编号k-1更大的结点通过。同样，在k到j的那条最短路径上也不会有比编号k-1更大的结点通过。因此，可以把求取一条由i到j的最短路径看成是如下的过程：首先需要决策哪一个结点是该路径上具有最大编号的中间结点k，然后就再去求取由i到k和由k到j这两对结点之间的最短路径。当然，这两条路径上都不可能有比k-1还大的中间结点。—————