带权有向图

第1页共19页中南大学《数据结构》课程设计题目带权有向图最短路径问题学生姓名学号指导教师学院信息科学与工程学院专业班级完成时间2013年7月2日第2页共19页目录第一部分课程设计报告................................3第一章、课程设计目的................................3第二章、课程设计内容和要求..........................32.1问题描述：....................................32.2设计要求：....................................3第三章、课程设计总体方案及分析......................43.1问题分析：....................................43.2概要设计......................................63.3详细设计......................................63.4调试分析.....................................143.5测试结果.....................................14第二部分课程设计总结...............................181．调试情况......................................182．程序的优缺点..................................183．心得体会......................................18第3页共19页第一部分课程设计报告第一章、课程设计目的通过对采用适当的存储结构实现带权有向图的存储，建立，输入、显示，以及使用Dijkstra算法，寻找和输出带权有向图中某个源点到其余各点的最短路径的实际程序设计，加深对图以及相关数据结构知识的掌握，初步具备相应的数据结构编程能力。第二章课程设计内容和要求2.1问题描述：采用适当的存储结构实现带权有向图的存储，建立，输入、显示，以及使用Dijkstra算法，寻找和输出带权有向图中某个源点到其余各点的最短路径。2.2设计要求：要求设计程序输出如下：第4页共19页(1)建立一个任意带权有向图（图的数据由用户输入），并在屏幕上显示出来；(2)使用Dijkstra算法求某点到另一个的最短路径；（3）在屏幕上输出路径；第三章、课程设计总体方案及分析3.1问题分析：1.带权有向图的建立存储：采用十字链表存储表示,构造有向图G，用邻接矩阵来存储图，用队列存储顶点以及弧度，方便求最短路径。2.最短路径的搜索：主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列，但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。Dijkstra算法流程图如下所示：第5页共19页开始定义全局变量dist[N]，v0,cost[N][N]初始化变量final[N],i,v,w,min,kK=0KNV=0VNfinal[v]=false;dist[v]=cost[v0][v];Yfinal[v0]=trueNi=0iN-1初始最短长度无穷大W=0WN!final[w]&&dist[w]minMin=dist[w]v=w;YYYW++加入新边final[v]=trueW=0WN!final[w]&&dist[v]+cost[v][w]dist[w]dist[w]=dist[v]+cost[v][w];YW++Ni=0iN-1iN-1输出dist[i]v0++;Yreturn0;NYNNI++NK++;NI++END第6页共19页3.2概要设计1.①采用十字链表存储表示,构造有向图G。②用邻接矩阵来存储图。③输出有向图④构建一个队列用于存储弧度⑤实现最短路径算法⑥屏幕上显示操作菜单2.本程序包含6个主要函数：(1)主函数main()(2)构造有向图的函数CreateDG(OLGraph*G)(3)输出有向图的函数Display(OLGraphG)(4)给有向图弧赋值的函数getcost(OLGraphG,int(*Visit)(VertexType))(5)输出邻接矩阵函数outarcs(OLGraphG)(6)Dijkstra算法ShortestPath_DIJ(OLGraphG)3.3详细设计实现概要设计中定义的所有数据类型，对各个操作给出伪代码算法。对于主程序和各个模块也给出相应的伪代码算法。1.带权有向图的建立采用十字链表存储表示,构造有向图G。intCreateDG(OLGraph*G){inti,j,k;ArcBox*p;VertexTypev1,v2;printf(\t请输入有向图的顶点数,弧数(请一次性输入，相互间用空格分开)\n);scanf(%d%d,&(*G).vexnum,&(*G).arcnum);第7页共19页printf(\t请输入%d个顶点的值(%d个字符，请一次性输入，相互间用空格分开):\n,(*G).vexnum,MAX_VERTEX_NAME);for(i=0;i(*G).vexnum;++i)//构造表头向量{scanf(%s%*c,&(*G).xlist[i].data);(*G).xlist[i].firstin=NULL;(*G).xlist[i].firstout=NULL;}for(i=0;i(*G).vexnum;++i){//初始化邻接矩阵for(k=0;k(*G).vexnum;++k){if(i!=k){(*G).arcs[i][k].adj=INFINITY;//设弧的权值最大值为100}else(*G).arcs[i][k].adj=0;}}printf(\t请输入%d条弧的弧尾和弧头(请一次性输入，相互间用空格分开):\n,(*G).arcnum);for(k=0;k(*G).arcnum;++k)//输入各弧并构造十字链表{scanf(%s%s%*c,&v1,&v2);i=LocateVex(*G,v1);j=LocateVex(*G,v2);p=(ArcBox*)malloc(sizeof(ArcBox));p-tailvex=i;p-headvex=j;p-hlink=(*G).xlist[j].firstin;p-tlink=(*G).xlist[i].firstout;第8页共19页(*G).xlist[j].firstin=(*G).xlist[i].firstout=p;//完成在入弧和出弧链表表头的插入}return1;}2.各个顶点用队列存储由求解操作stacksearch()函数进行//构造一个空队列QintInitQueue(SqQueue*Q){(*Q).base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!(*Q).base)//存储分配失败exit(0);(*Q).front=(*Q).rear=0;return1;}//若队列Q为空队列,则返回1,否则返回0intQueueEmpty(SqQueue*Q){if((*Q).front==(*Q).rear)return1;elsereturn0;}//插入元素e为Q的新的队尾元素intEnQueue(SqQueue*Q,QElemTypee){if(((*Q).rear+1)%MAXQSIZE==(*Q).front)//队列满return0;第9页共19页(*Q).base[(*Q).rear]=e;(*Q).rear=((*Q).rear+1)%MAXQSIZE;return1;}//若队列不空,则删除Q的队头元素,用e返回其值,并返回1;否则返回0intDeQueue(SqQueue*Q,QElemType*e){if((*Q).front==(*Q).rear)//队列空return0;*e=(*Q).base[(*Q).front];(*Q).front=((*Q).front+1)%MAXQSIZE;return1;}//将一个队列M的值赋给另外的一个队列LvoidSqQueuecpy(SqQueue*L,SqQueue*M){inti;(*L).front=(*M).front;(*L).rear=(*M).rear;for(i=(*M).front;i(*M).rear;++i){(*L).base[i]=(*M).base[i];}}//输出队列voidoutSqQueue(OLGraphG,SqQueue*S){inti;for(i=(*S).front;i(*S).rear;++i){printf(%s\t,GetVex(G,(*S).base[i]));}}第10页共19页voidClearQueue(SqQueue*Q){inti;for(i=(*Q).front;i(*Q).rear;++i){(*Q).base[i]=0;}(*Q).front=(*Q).rear=0;}3.输出有向图和邻接矩阵//输出有向图GvoidDisplay(OLGraphG){inti;ArcBox*p;printf(\t**********************图G共有%d个顶点,%d条弧:***************************\n,G.vexnum,G.arcnum);for(i=0;iG.vexnum;i++){printf(\t**********************顶点%s:入度:,G.xlist[i].data);p=G.xlist[i].firstin;while(p){printf(%s,G.xlist[p-tailvex].data);p=p-hlink;}printf(出度:);p=G.xlist[i].firstout;while(p){printf(%s,G.xlist[p-headvex].data);p=p-tlink;}printf(\n);}第11页共19页}//输出邻接矩阵voidoutarcs(OLGraphG){inti,j;for(i=0;iG.vexnum;i++){printf(\t%s,G.xlist[i].data);}printf(\n);for(i=0;iG.vexnum;i++){printf(%s,G.xlist[i].data);for(j=0;jG.vexnum;j++){if(j==G.vexnum-1)printf(\t%d\n,G.arcs[i][j].adj);elseprintf(\t%d,G.arcs[i][j].adj);}}}4.求最短路径用Dijkstra算法求从某个顶点到其余各顶点的最短路径voidShortestPath_DIJ(OLGraphG){inti,w,v,min,no;VertexTypeVstart;//Vstart记录输入顶点intv0;//v0为输入顶点序号printf(\t输入开始的顶点为:);gets(Vstart);v0=LocateVex(G,Vstart);intfinal[MAX_VERTEX_NUM];//记录是否已经找到从某个顶点到顶点finanl[i]的最短路径intD[MAX_VERTEX_NUM];第12页共19页SqQueueShorte