资源描述：
《《短路问题》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二节最短路问题§2.1基本概念与基本定理§2.2最短路的算法精品课程《运筹学》第二节最短路问题最短路问题是重要的最优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路选择，设备更新、投资等问题，而且经常被作为一个基本工具，用于解决其它的优化问题。精品课程《运筹学》§2.1基本概念与基本定理在有向图G中，设P是有向图D=（V，E）中从顶点u到v为点弧交替的序列。如果序列中每一条弧的始点和终点恰好分别是与它前后相邻的顶点，则称这个序列P是D中的一条路。精品课程《运筹学》设已给定了
2、一个有向赋权图D=(V,A,w);wij≥0,((u,v)∈A)，若u是D中的一条路，则称w(u)=∑wij为路u的总权数（或称为路长）。设u,v是D=(V,A,w)中取定的两个点，存在从u到v的路，称从u到v的路中总权数最小者为最短路。对于最短路，显然有下列定理成立.精品课程《运筹学》定理6.2.1有向图D=(V,A,w)，V={1,2,..,n}，记dj为点1到点j的最短路的路长且不妨设当1＜i＜j时有0＜di＜dj＜∞,则有d1=0及dj=min{di+wij}(j=1,2,…,n),其中wi
3、j为点i到点j的弧的权数。精品课程《运筹学》§2.2最短路的算法1．Dijkstra算法（适用于所有权非负的情况）Dijkstra算法是E.W.Dijkstra于1959年提出的，是目前公认的对所有权非负的情况的最好算法。精品课程《运筹学》设D=(V,A,w)满足上述定理条件，则有以下算法：①令u1=0,uj﹦wij(若不存在点1到点j的路则记w1j=∞),p={1},T={2,3,…,n}(p为以确定的点之集，T为未确定的点之集)；②（指出永久标号）在T中找出一点k使得uk={uj}。令p:=p∪
4、{k},T=T{k},若T=空集算法结束，并令di=ui(I=1,2,…n),否则进入(3)；③（修改临时标号）对T中每一个点j，令uj=min{uj,uk+wij}，然后返回②。精品课程《运筹学》例6.2.1求图6-2-1中点v1到其它各点的最短路（弧旁的数字表示距离）。解用Dijkstra算法，这里只画出每步所得图得标号的变化情况，即图6-2-2，小方框内数字即为各顶点到v1的最短路。写出计算结果，具体步骤请读者自己完成。精品课程《运筹学》精品课程《运筹学》2.最短路的矩阵算法（适用于所有权非
5、负的情况）最短路的矩阵算法是将图表示成是矩阵形式，然后利用矩阵表计算出最短路。矩阵算法的原理与Dijkstra算法标号算法完全相同，只是它采用了矩阵形式，显得更为简洁，有利于计算机计算。下面先介绍图的矩阵表示。精品课程《运筹学》（1)图的矩阵表示无权图矩阵表示：两顶点之间有边相连的记为“1”，无边相连的记为“0”，对角线上记为“0”。赋权无向图矩阵表示：两顶点之间有边相连的，写上它们的权数，无边相连的记为“∞”，对角线上记为0。赋权有向图的矩阵表示：左边第一列为各条弧的起点。在每一行中，以该点为起点
6、，按弧的方向，依次填上到各点的权，若没有到该点的弧，则权数为“∞”。精品课程《运筹学》（2）最短路的矩阵算法最短路的矩阵算法步骤如下：①将图表示成矩阵形式。②确定起点行，将其标号确定为0，将相应的列在矩阵表中划去。③在已标号的行中未划去的元素中，找出最小元素aij,把它圈起来，此时把第j列划去，同时给第j行标号aij，并把第j行中未划去的各元素都加上aij。这标号的含义同标号算法。精品课程《运筹学》若还存在某些行未标号，则返回③。如果各行均已获得标号（或终点行已获得标号），则终止计算。并利用倒向追踪
7、，求得自起点到各点的最短通路。3．Ford算法(适用于含负权弧的情况)设D=(V，A，w)为有负权弧的有向图，不妨设图D中任两点从vi到vj均有弧联结（若没有可认为(vi，vj)存在且wij=+∞）且设D中只有n（n为常数）个点。精品课程《运筹学》则d(j)可由以下迭代关系d(1)(j)=w1j(j=1,2,…,n)与d(k)(j)={d(i)+wij}(k=2,3,…)求出。若迭代到某一步k时，有d(k)(j)=d(k-1)(j)(j=1,2,3,…n)则运算结束，且d(j)=d(k)(j)(j=
8、1,2,3,…n)精品课程《运筹学》
