第二第二节 最短路最短路问题2.1 根本概念与根本定理根本概念与根本定理2.2 最短路的算法最短路的算法第二节 最短路问题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)中取定的两个点，存在从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的路那么记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.最短路的矩阵算法适用于一切权非负的情况 最短路的矩阵算法是将图表示成是矩阵方式，然后利用矩阵表计算出最短路。矩阵算法的原理与Dijkstra算法标号算法完全一样，只是它采用了矩阵方式，显得更为简约，有利于计算机计算。 下面先引见图的矩阵表示。 n1) 1) 图的矩的矩阵表示表示n 无无权图矩矩阵表表示示：两两顶点点之之间有有边相相连的的记为“1“1，无无边相相连的的记为“0“0，对角角线上上记为“0“0。赋权无无向向图矩矩阵表表示示：两两顶点点之之间有有边相相连的的，写写上上它它们的的权数数，无无边相相连的的记为“，对角角线上上记为0 0。n 赋权有有向向图的的矩矩阵表表示示：左左边第第一一列列为各各条条弧弧的的起起点点。在在每每一一行行中中，以以该点点为起起点点，按按弧弧的的方方向向，依依次次填填上上到到各各点点的的权，假假设没没有有到到该点点的弧，那么的弧，那么权数数为“。 2 2最短路的矩最短路的矩阵算法算法 最短路的矩最短路的矩阵算法步算法步骤如下：如下： 将将图表示成矩表示成矩阵方式。方式。 确确定定起起点点行行，将将其其标号号确确定定为0 0，将将相相应的的列在矩列在矩阵表中划去。表中划去。 在在已已标号号的的行行中中未未划划去去的的元元素素中中，找找出出最最小小元元素素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=1,2,3,n)(j=1,2,3,n)那么运算那么运算终了，且了，且 d(j)=d(k)(j) d(j)=d(k)(j) (j=1,2,3,n)(j=1,2,3,n)