2016课程设计.等多个文件

第1章需求分 第2章动态规划方法的介 第3章基本理论知识和方 第4章实验分 参考文 附录设计系统部分源代 1求分在的实际生活中常常会出现这样的问题：俩个城市之间，是否有道路可通,在有多条通路的情况下，哪一条总程最短；在公路中，即从某一城市出发，途中必须经过哪几个城市才会使花费的总代价最少。通常近距离时可以凭经验或者作出判断，但若俩个城市相距较远且中间又有多条通路，又如何作出判断呢？这时可以一个简单的程序建立一个交通咨询系统，作出最优决策。在这个系统中，可以把地图模型化为一个图，结点表示一段公路的起点和终点，边的权值表示公路的长度，的目标是从起点出发找到一条到达2态规划方法的介将交通网络图视为带权有向本文中只对俩个城市之间的距离进行）有向图G，然后将这个赋权网络图输入到计算机组中（n表示城市的个数。定义带权有向定义①若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e的权,则称这种图为赋权图,G=G(V,E,W)G=G(V,E)

We

,eEG,u是vi到vj1Wu的权则称Wu为u的长长最小的i到vj的路Wu称为最短路径。nui到vn的通路u使全长最短即 We迪杰斯特拉算法流城市之间最短路径（城市之间最短路径（dijkstra算法2-1dijkstra算法计算最短路弗洛伊德算法流n次，这样便可求得由用户由用户城市之间最短路径（floyd算法最后求的从起点城市到最后求的从起点城市到终点城市的最短路径的间经过的城市和从起点城市到途经2-4-1floyd3本理论知识和方最短路基本介60年代以前就卓有成效了其中对赋权图j0有效算法是由荷兰著名计算机Dijsta在1959年首次该算法能够解决两指点间的最短路G中一特定点到其它各顶点的最短路径。DijkstraFordFord算法,但在现实生活中 在wijDijkstra基本定

定义①若图G=G(V,E)eW(e),e的权,则称这种图为赋权图,G=G(V,E)

We

,eEG,u是vi到vj的路Wu的权,Wu为u的长,长最小的vi到vj的路Wu若要找出从vi到vn的通路u,使全长最短,即minWuWe 迪杰斯特拉算基本定一般的表述通常有两种方式，一种用和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用和临时标号的方式。基本原DDvD[3]=2v32。这里强调相对就是说在算法过程中D的值是在不断近最终结果但在过程中不一定就等于最短路径长度。vviDD为∞。显然，长度为D[j]=Min{D|vi∈V}v(v,vj)。那么，vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)vvkD[j]和从vjvkS为已求得最短路径的终点的集合，则可证明：下一条最短路径（X）或者是弧(v,x)S中的顶点而最后XD[j]=Min{D|vi∈V-S}其中，D或者是弧(v,vi)D[k](vk∈S)和弧(vk,vi)上的权值之和。迪杰斯特拉算MAXCOSTSvv出发到图上其viD=arcs[LocateVex(G,v),i]vi∈V2）vj，D[j]=Min{D|vi∈V-S3）vV-Svk可达的最短路径长度。G=(V,E)EwV0到其余各点的最短思想内V0SV0T中任何顶点的最短路SV0TV0SV0到TVkV0Vk的直接路径的权值；或是V0SVk的路径权值之和（反证法可证弗洛伊德算基本定n次，这样便可求得基本原costvivjvivj存cost[i][j]n次试探。首先考虑vivj1v2,即如果（vi,…,v2）和（v2,…,vj）1vi,..,v2,…,vjvivj2的最短路径。vivj12v3,n次比较，vivj的最短路径。按此方法，可以同时求得各对顶点间的最短路径。n阶方阵序列：A(0),A(1),…,A(n)从上述计算公式可见，A(1)[i][j]vivj1A(n)[i][j]vivj俩种算法的比从算法的基本思想而言，Dijkstra算法的基本思想是以Vs为起点,从图中找出与其距离最短的顶点。假设该点为Vi,然后再以Vi作为参照点,从余下的顶点中找出与其距离最短的顶点,依次类推直到所有的顶点都对比完为止至止,Vs到各顶点的最短距离就已经求出来了。至于具体的最短路径,常用的方法是“反向追踪法。即从终点出发,“顺藤摸瓜”找到最短距离上的各个点,按照有向图的方向,就可以得到最短路径。Floyd算法的基本思想是:从Vs到Vt的最短路径是以下各种可能路径中的长度最小的那条。若<Vs,Vt>存在,则存在路径{Vs,Vt}。(路径中不含有其它顶点) 若<Vs,V1>,<V1,Vt>存在,则存在路径{Vs,V1,Vt}。(路径中所含顶点序号不大于1) 若<Vs,V2>,<V2，Vt>存在,则存在一条最短路径{Vs,„V2„Vj}(路径中所含顶点序号不大于2)依次类推,则Vs到Vt的最短路径应是上述这些路径中路径长度最小者。两种算法的基本思想不同,导致了两种算法结果的不同对于Dijkstra算法而言,其结果是可求出从某一个顶点到其余各顶点的最短路径。而Floyd算法的结果是可以得出图中任意两对顶点之间的最短路径。而从算法步骤而言，Floyd算法是从邻接矩阵出发,而且最短路径可以从序号矩阵中找出来。最短路径的权值从距离矩阵中得出。在许多情况下,图中的权重可能是负值。Dijkstra算法要求每一个权重必须大于或等于零,这是该算法Floyd算法计算最短路径时间4验分4.1结随机选择6个城市作为一个交通系统，这6个城市分别为：长春，哈尔滨，，G4-14-2在c语言中，把这些城市的信息用一个c结构体数组（city[][]）来保存typedef{charname[99];charnum;intn*n2（n表示城市的个数2G(INF表示无穷，即俩个城市之间没有通路4-3g[6][6]2city4-4程序运行图迪杰斯特拉算法案算法步S={V0},T={其余顶点}，T中顶点对应的距离值TWSTWV0Vi的距离值缩短，2、3SW=Vi流程out函数，获取dis[][]4-5dijkstra算法流分析，调4-6程序运行图305060注：此处的最短距离是指从起点城春到各个顶点城市的最短距离；弗洛伊德算法案算法步uvwuwv比已知的GViVjG[i,j]=d，d表示该路的长度；否则G[i,j]=无穷大。定义一个矩阵D用来记录所点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点图中，比较插点后的距离与原来的距离，G[i,j]=D中则包含了最短通路径的信息。V5V1DD(5,1)=3V5V1V3，路径为{V5,V3,V1}D(5,3)=3V5V3D(3,1)=1V3V1流程4-7floyd分析，调4-8程序运行图305060注：此处的最短距离是指从起点城春到各个顶点城市的最短距离；结花费变得最少。对于实际的交通网络图，可以把城市之间的信息于数据库中，通过对于对于最短路径算法，不仅可以用于出行的计算，还可以用 地图等网络地图的应抢修、交通指挥、GPS导航等行业应用中使用的非常广泛，同时最短路径也是图论研究中的题可以通过图的相关知识来解决，特别是在解决最短路径问题中，显得尤为重要。参考文1刁在筠，，宿洁，[M].：高等教育2谭浩强.C语言程序设计[M].：3谢金星，邢文训.网络优化[M].：4严蔚敏，吴伟民.数据结构（c语言版）[M].：5、主编《图论及其算法，中国科学技术大学，2005年6熊伟，运筹学，第二版，：机械工业，20117，数学建模基础，第二版，：科学，20118韩中庚宋明武邵广纪，数学建模竞赛获奖精选与点评，：科学，2007计系统部分源代C语言（1）intd[100],path[100],final[100];inttypedef{charname[99];charnum;intvoiddijkstra(ints,intn)//{inti,j,k,mi;{}{intmin=999;{}{}}}voidout(ints,intn)//{intb[100];//bs到某顶点的最短路径上的各个顶点的编点，从后向前inti,j,p,m;{printf("从起点城市%d到顶点城市%d不存在路径{//printf("从源点%d到顶点%d的最短路径长度为：%d\n",s,i,d[i]);{}for(j=m;j>=0;j--{}}}}{ints,n=6;inti,j;charfrist;charcityc[100];strcpy(c[1].name,"哈尔滨strcpy(c[2].name,"strcpy(c[3].name,"沈阳strcpy(c[4].name,"石家庄printf("请选择起点城市和终点城春（A，哈尔滨(B),（C，沈阳(D)，石家(E)，太原scanf("%c%c",&frist,&last);{{printf("您选择的起点城市是%s，终点城市是}}for(intx=0;x<n;x++)for(inti=0;i<n;i++)printf(":%d,:%s}2：#defineINF99999typedef{charname[99];charnum;intint{intintn,i,j,k;intintdis[10][10];charfrist;charlast;cityc[100];strcpy(c[0].name,"长春strcpy(c[1].name,"哈尔滨strcpy(c[2].name,"strcpy(c[3].name,"沈阳strcpy(c[4].name,"石家庄printf("请选择起点城市和终点城春（A，哈尔滨(B),（C，沈阳(D)，石家