《短路问题 》ppt课件

1、第二节 最短路问题n 最短路问题是重要的最优化问题之一，它不仅可以直接运用于处置消费实际的许多问题，如管道铺设、线路选择，设备更新、投资等问题，而且经常被作为一个根本工具，用于处置其它的优化问题。 2.1 根本概念与根本定理 在有向图G中，设P是有向图 D=V，E中从顶点u到v为点弧交替的序列。假设序列中每一条弧的始点和终点恰好分别是与它前后相邻的顶点，那么称这个序列P是D中的一条路。 设 已 给 定 了 一 个 有 向 赋 权 图D=(V,A,w);wij0,(u,v)A)，假设u是D中的一条路，那么称w(u)=wij为路u的总权数或称为路长。 设u,v是D=(V,A,w)中取定的两个点，存

2、在从u到v的路，称从u到v的路中总权数最小者为最短路。 对于最短路，显然有以下定理成立. 定理6.2.1 有向图D=(V,A,w)，V=1,2,.,n，记 dj为点1到点j的最短路的路长且无妨设当1ij时有0didj,那么有d1=0及dj=mindi+wij(j=1,2,n),其中wij为点i到点j的弧的权数。 2.2 最短路的算法1Dijkstra算法适用于一切权非负的情况 Dijkstra算法是E.W. Dijkstra于1959年提出的，是目前公认的对一切权非负的情况的最好算法。 设D=(V,A,w)满足上述定理条件，那么有以下算法： 令u1=0,ujwij(假设不存在点1到点j的路那么

3、记w1j=),p=1,T=2,3,n(p为以确定的点之集，T为未确定的点之集)； 指出永久标号在T中找出一点k使得uk=uj。令p:=pk,T=Tk,假设T=空集算法终了，并令di=ui(I=1,2,n),否那么进入(3)； 修 正 暂 时 标 号 对 T 中 每 一 个 点 j ， 令uj=minuj,uk+wij，然后前往。 例6.2.1求图6-2-1中点v1到其它各点的最短路弧旁的数字表示间隔。 解 用Dijkstra算法，这里只画出每步所得图得标号的变化情况，即图6-2-2，小方框内数字即为各顶点到v1的最短路。写出计算结果，详细步骤请读者本人完成。 2.最短路的矩阵算法适用于一切权非

4、负的情况 最短路的矩阵算法是将图表示成是矩阵方式，然后利用矩阵表计算出最短路。矩阵算法的原理与Dijkstra算法标号算法完全一样，只是它采用了矩阵方式，显得更为简约，有利于计算机计算。 下面先引见图的矩阵表示。 n1) 1) 图的矩阵表示图的矩阵表示n 无权图矩阵表示：两顶点之间有边相连的无权图矩阵表示：两顶点之间有边相连的记为记为“1“1，无边相连的记为，无边相连的记为“0“0，对角线上，对角线上记为记为“0“0。赋权无向图矩阵表示：两顶点之间。赋权无向图矩阵表示：两顶点之间有边相连的，写上它们的权数，无边相连的记有边相连的，写上它们的权数，无边相连的记为为“，对角线上记为，对角线上记为0

5、 0。n 赋权有向图的矩阵表示：左边第一列为赋权有向图的矩阵表示：左边第一列为各条弧的起点。在每一行中，以该点为起点，各条弧的起点。在每一行中，以该点为起点，按弧的方向，依次填上到各点的权，假设没有按弧的方向，依次填上到各点的权，假设没有到该点的弧，那么权数为到该点的弧，那么权数为“。 2 2最短路的矩阵算法最短路的矩阵算法 最短路的矩阵算法步骤如下：最短路的矩阵算法步骤如下： 将图表示成矩阵方式。将图表示成矩阵方式。 确定起点行，将其标号确定为确定起点行，将其标号确定为0 0，将相应的，将相应的列在矩阵表中划去。列在矩阵表中划去。 在已标号的行中未划去的元素中，找出最小在已标号的行中未划去的

6、元素中，找出最小元素元素aij ,aij ,把它圈起来，此时把第把它圈起来，此时把第j j列划去，同列划去，同时给第时给第j j行标号行标号aij aij ，并把第，并把第j j行中未划去的各行中未划去的各元素都加上元素都加上aij aij 。这标号的含义同标号算法。这标号的含义同标号算法。 假设还存在某些行未标号，那么前往。假设各行均已获得标号或终点行已获得标号，那么终止计算。并利用倒向追踪，求得自起点到各点的最短通路。3 Ford算法 (适用于含负权弧的情况) 设D=(V，A，w)为有负权弧的有向图，无妨设图D中任两点从vi 到vj均有弧结合假设没有可以为(vi，vj)存在且wij=+且设D中只需nn为常数个点。那么那么d(j)d(j)可由以下迭代关系可由以下迭代关系d(1)(j)=w1j (j=1,2,n)d(1)(j)=w1j (j=1,2,n)与与d(k)(j)=d(i)+wij (k=2,3,)d(k)(j)=d(i)+wij (k=2,3,)求出。求出。 假设迭代到某一步假设迭代到某一步k k时，有时，有 d ( k ) ( j ) = d ( k - 1 ) ( j ) d ( k ) ( j ) = d ( k - 1 ) ( j ) (j