第二部分最短路问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精品课程运筹学,第二节 最短路问题,2.1 基本概念与基本定理,2.2 最短路的算法,精品课程运筹学,第二节 最短路问题,最短路问题是重要的最优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，,如管道铺设、线路选择，设备更新、投资等问题，而且经常被作为一个基本工具，用于解决其它的优化问题,。,精品课程运筹学,2.1,基本概念与基本定理,在有向图G中，设P是有向图 D=（V，E）中从顶点u到v为点弧交替的序列。如果序列中每一条弧的始点和终点恰好分别是与它前后相邻的顶点，则称这个序列P是D中的一条,路,。,精品课程运筹学,设已给定了一个有向赋权图D=(V,A,w);w,ij,0,(u,v)A)，若u是D中的一条路，则称w(u)=w,ij,为路u的总权数（或称为路长）。,设u,v是D=(V,A,w)中取定的两个点，存在从u到v的路，称从u到v的路中总权数最小者为最短路。,对于最短路，显然有下列定理成立,.,精品课程运筹学,定理,6.2.1,有向图,D=(V,A,w,),，,V=1,2,.,n,，,记,d,j,为点,1,到点,j,的最短路的路长且不妨设当,1,i,j,时有,0,d,i,d,j,则有,d,1,=0,及,d,j,=mind,i,+,w,ij,(j=1,2,n),其中,w,ij,为点,i,到点,j,的弧的权数。,精品课程运筹学,例,6.2.1,求图,6-2-1,中点,v,1,到其它各点的最短路（弧旁的数字表示距离）。,解,用,Dijkstra,算法，这里只画出每步所得图得标号的变化情况，即图,6-2-2,，小方框内数字即为各顶点到,v,1,的最短路。写出计算结果，具体步骤请读者自己完成。,精品课程运筹学,精品课程运筹学,2,.,最短路的矩阵算法,（适用于所有权非负的情况）,最短路的矩阵算法是将图表示成是矩阵形式，然后利用矩阵表计算出最短路。矩阵算法的原理与,Dijkstra,算法标号算法完全相同，只是它采用了矩阵形式，显得更为简洁，有利于计算机计算。,下面先介绍图的矩阵表示。,精品课程运筹学,（1),图的矩阵表示,无权图矩阵表示：两顶点之间有边相连的记为“,1,”，无边相连的记为“,0,”，对角线上记为“,0,”。赋权无向图矩阵表示：两顶点之间有边相连的，写上它们的权数，无边相连的记为“”，对角线上记为,0,。,赋权有向图的矩阵表示：左边第一列为各条弧的起点。在每一行中，以该点为起点，按弧的方向，依次填上到各点的权，若没有到该点的弧，则权数为“”。,精品课程运筹学,（2）最短路的矩阵算法,最短路的矩阵算法步骤如下：,将图表示成矩阵形式。,确定起点行，将其标号确定为0，将相应的列在矩阵表中划去。,在已标号的行中未划去的元素中，找出最小元素a,ij,把它圈起来，此时把第j列划去，同时给第j行标号a,ij,，并把第j行中未划去的各元素都加上a,ij,。这标号的含义同标号算法。,精品课程运筹学,若还存在某些行未标号，则返回。如果各行均已获得标号（或终点行已获得标号），则终止计算。并利用倒向追踪，求得自起点到各点的最短通路。,3,Ford,算法,(,适用于含负权弧的情况,),设,D=(V,，,A,，,w),为有负权弧的有向图，不妨设图,D,中任两点从,v,i,到,v,j,均有弧联结（若没有可认为,(,v,i,，,v,j,),存在且,w,ij,=+,）且设,D,中只有,n,（,n,为常数）个点。,精品课程运筹学,则,d(j),可由以下迭代关系,d,(1),(j)=,w,1j,(j=1,2,n),与,d,(k),(j)=d(i)+,w,ij,(k=2,3,),求出。,若迭代到某一步,k,时，有,d,(k),(j)=d,(k-1),(j)(j=1,2,3,n),则运算结束，且,d(j)=d,(k),(j)(j=1,2,3,n),精品课程运筹学,