第一部分最短路径问题

第一部分：最短路1在的实际生活中常常会出现这样的问题：俩个城市之间，是否有道路可通,在有多条通路的情况下，哪一条总程最短；在公路中，即从某一城市出发，途中必须经过哪几个城市才会使花费的总代价最少。通常近距离时可以凭经验或者作出判断，但若俩个城市相距较远且中间又有多条通路，又如何作出判断呢？这时可以一个简单的程序建立一个交通咨询系统，作出最优决策。在这个系统中，可以把地图模型化为一个图，结点表示一段公路的起点和终点，边的权值表示公路的长度，的目标是从起点出发找到一条到2态规划方法的介将交通网络图视为带权有向n*n的数组中（n表示城市的个数定义①若图G=G(V,E)eW(e),e的权,则称这种图为赋权图,记为G=G(V,E,W)G=G(V,E)We0,eEG,u是vi到vj1Wu为uW 的长,长最小的为u

W到到

若要找出从vi到vn的通路u,使全长最短,minWuW城市之间最短路径（dijkstra城市之间最短路径（dijkstra算法点城市由用户输入起利用

n次，这样便可求得由用户由用户城市之间最短路径（floyd算法最后求的从起点城市到终点城市的最短路径的最后求的从起点城市到终点城市的最短路径的间经过的城市和从起点城市到途经2-4-1floyd3本理论知识和方最短路对最短路径问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图wij0的有效算法是由荷兰著名计算机E.W.Dijkstra在1959年首次,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路径。FordFord算法,它能有效地解决含有负权的最短路问题。但在现实生活中 在wijDijkstra

G=G(V,E)是赋权图且We0,eEG,u是vi到vj的路Wu的权Wu为u的长,长最小的vi到

W的 称为最短路径若要找出从vi到vn的通路u,使全长最短,minWuW 方式，这里均采用和临时标号的方式。D[3]=2v32。这里强调相它的初始状态为：若从vviD为弧上的权值；否则置D为∞。显然，长度为D[j]=Min{D|vi∈V}v出发的长度最短的一条最短路径。此路径为(v,vj)。那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)vvkD[j]和从vjvk的弧上的权值之和。一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后X的路径。因此，下一条长度次短的最短路径的长度必是D[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-S}3v出发到集合V-Svk可达的最短路径长度。G=(V,E)EwV0到其余各点的最短V0到TVkV0Vk的直接路径的权值；或是V0S中顶点到Vk的路径权值之和（反证法可证n次，这样便可求得costvivjvivj存v2,即如果（vi,…,v2）和（v2,…,vj）1最后求得的必是从vivj的最短路径。按此方法，可以同时求得各对顶点间的最短路径。A(k-1)[i][k]+A(k-从算法的基本思想而言，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算法计算最短路径时间44.1结有向图G4-14-2typedef{charnum;int4-3g[6][6]2city4-4程序运行图S={V0},T={其余顶点}，T中顶点对应的距离值dis[][]4-6程序运行图305060uvwuwv比已知的否则G[i,j]=无穷大。定义一个矩阵D用来记录所点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点图中，比较插点后的距离与原来的距离，G[i,j]=的信息，而在D中则包含了最短通路径的信息。4-7floyd4-8程序运行图305060第五 结城市之间的最短路径问题。可以解决在生产管理中，在交通和通讯领域遇到的沿着哪一都可以看成是在给定的图中，求最短路径的问题，这些都体现的离散数学与计算机的结附录设计系统部分源inttypedefstruct{charnum;intvoiddijkstra(ints,intn)//{{}{intmin=999;{}{}}}voidout(ints,intn)//{inti,j,p,m;{printf("从起点城市%d到顶点城市%d不存在路径\n",s,i);{{}for(j=m;j>=0;j--{}}}}{ints,n=6;inti,j;charcityc[100];strcpy(c[1].name,"哈尔滨strcpy(c[2].name,"strcpy(c[3].name,"沈阳strcpy(c[4].name,"石家庄{{printf("您选择的起点城市是%s，终点城市是}}for(intx=0;x<n;x++)printf(":%d,:%s}代码2：#defineINFtypedef{charnum;intint{intintintdis[10][10];charcharlast;strcpy(c[0].name,"长春strcpy(c[1].name,"哈尔滨strcpy(c[2].name,"strcpy(c[3].name,"沈阳strcpy(c[4].name,"石家庄{{printf("您选择的起点城市是%s，终点城市是}}//