1、 最短路问题最短路问题一、最短路问题一、最短路问题例例 下图为单行线交通网，每弧旁的数字表示通过这条下图为单行线交通网，每弧旁的数字表示通过这条 线所需的费用。现在某人要从线所需的费用。现在某人要从v1出发，通过这个交出发，通过这个交 通网到通网到v8去，求使总费用最小的旅行路线。去，求使总费用最小的旅行路线。v2v523464v3v1v4v6121061210v8v9v72363从从v1到到v8：P1=（v1，v2，v5，v8）费用费用 6+1+6=13P2=（v1，v3，v4，v6，v7，v8）费用费用 3+2+10+2+4=21P3=从从v1到到v8的旅行路线的旅行路线 从从v1到到v8
2、的路。的路。旅行路线总费用旅行路线总费用 路上所有弧权之和。路上所有弧权之和。最短路问题中，不考虑有向环、并行弧。最短路问题中，不考虑有向环、并行弧。v2v523464v3v1v4v6121061210v8v9v72363最短路问题最短路问题 给定有向网络给定有向网络D=（V，A，W），任意弧），任意弧aijA，有权有权w（aij）=wij，给定，给定D中的两个顶点中的两个顶点vs，vt。设。设P是是D中从中从vs到到vt的一条路，定义路的一条路，定义路P的权（长度）是的权（长度）是P中中所有弧的权之和，记为所有弧的权之和，记为w（P）。最短路问题就是要在）。最短路问题就是要在所有从所有从vs
3、到到vt的路中，求一条路的路中，求一条路P0，使，使(P)min)(PP0ww 称称P0是从是从vs到到vt的最短路。路的最短路。路P0的权称为从的权称为从vs到到vt的路长。记为的路长。记为ust。二、二、Dijkstra算法算法 当所有当所有 wij 0 时，时，本算法是用来本算法是用来求给定点求给定点vs到到任一个点任一个点vj 最短路最短路的公认的最好方法。的公认的最好方法。事实：如果事实：如果P是是D中从中从vs到到vj的最短路，的最短路，vi是是P中的一中的一个点，那么，从个点，那么，从vs沿沿P到到vi的路是从的路是从vs到到 vi的最短路。的最短路。最短路的子路也是最短路。最短
4、路的子路也是最短路。思想：将思想：将D=（V，A，W）中）中vs到所有其它顶点的最短到所有其它顶点的最短 路按其路按其路长路长从小到大排列为：从小到大排列为：u0 u1 u2 unu0表示表示vs到自身的长度，相应最短路记为：到自身的长度，相应最短路记为：P0，P1，P2，Pn，sivswu,vi0X1000min ,XVX X 则则记记取最小值的点为取最小值的点为v1，P1=P（vs，v1）假定假定 u0，u1，uk的值已求出，对应的最短路的值已求出，对应的最短路分别为分别为P1=P（vs，v1），），P2=P（vs，v2），），Pk=P（vs，vk）P1一定只有一条弧。一定只有一条弧。记记
5、 kkkskvvvvXVX ,.,X21 则则 ),w(miniXX1vvuuivvkkki 使上式达到最小值的点使上式达到最小值的点v 可取为可取为vk+1。计算过程中可采用标号方法。计算过程中可采用标号方法。Xk中的点，中的点，ui 值是值是vs 到到vi 的最短路长度，相应的的最短路长度，相应的点记点记“永久永久”标号；标号；XK中的点，中的点，ui值是值是vs到到vi的最短路长度的上界，的最短路长度的上界，相应的点记相应的点记“临时临时”标号，供进一步计算使用。标号，供进一步计算使用。前点标号前点标号 i:表示点表示点vs到到vj的最短路上的最短路上vj的前一点。的前一点。如如 i=m
6、，表示，表示vs到到vj的最短路上的最短路上vj前一点是前一点是vm。1,6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,1,1,11,1,1,1,31,6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,1,1,11,1,1,1,31,6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,1,31,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363
7、v60,01,4,111,11,1,1,1,31,61,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,1,33,53,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,31,3,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,31,3,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v6
8、0,04,111,11,2,61,1,31,3,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11,2,61,1,31,3,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11,2,65,121,35,93,5图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11,2,65,121,35,9Dijkstra算法步骤：算法步骤：第第1步：令步：令us=0，uj=wsj （1jn）若）若asj
9、 A，则，则第第2步：步：(选永久标号选永久标号)在在XK中选一点中选一点vi，满足，满足 第第3步：（给点步：（给点vi永久性标号）永久性标号）第第4步：步：(修改临时标号修改临时标号)对所有对所有 如果如果 ,Xv 1kj jijiuwu 令令 j=i，uj=ui+wij否则否则,i,uj 不变不变,把把k换成换成k+1，返回第返回第2步。步。jXviuminu Kj 如果如果ui=+，停止，停止，令令Xk+1=Xkvi,Xk+1=Xkvi令令wsj=+,X0=vs,X0=VX0,k=0,i=0(0 jn）从从vs到到XK中各点没有路；否则，转第中各点没有路；否则，转第3步。步。如果如果X
10、k+1=，结束，到所有的点的最短路已经求结束，到所有的点的最短路已经求得得；否则，转第；否则，转第4步。步。例例 用用Dijkstra算法求前面例子中从算法求前面例子中从v1到各点的最短路。到各点的最短路。解：解：u1=0，u2=6，u3=3，u4=1，u5=u6=u7=u8=u9=+，j=1 （j=2，3，9）X0=v1，X0=v2，v3，v9v2v523464v3v1v4v6121061210v8v9v72363K=0 minu2，u3，u4，u5，u6，u7，u8，u9 =min6，3，1，=1=u4 点点v4得永久标号，得永久标号，4=1，X1=v1，v4，X1=v2，v3，v5，v6
11、，v7，v8，v9，在所有在所有vjX1中，中，u6=，u4+w46=1+10=11，即即 u4+w46 u6 修改临时标号修改临时标号u6=11，6=4，其余标号不变。，其余标号不变。v2v523464v3v1v4v6121061210v8v9v72363K=0+1=1 minu2，u3，u5，u6，u7，u8，u9 =min6，3，11，=3=u3 点点v3得永久标号，得永久标号，3=1，X2=v1，v4，v3，X2=v2，v5，v6，v7，v8，v9，u2=6，u3+w32=3+2=5，即即 u3+w32 u2 修改临时标号修改临时标号u2=5，2=3，其余标号不变。，其余标号不变。在所
12、有在所有vjX2中中，k=2+1=3 minu5，u6，u7，u8，u9 =min6，11，=6=u5 点点v5得永久标号，得永久标号，5=2，X4=v1，v4，v3，v2，v5，X4=v6，v7，v8，v9，u6=11，u5+w56=6+4=10，即即 u5+w56 u6 u7=，u5+w57=6+3=9，即即 u5+w57 u7 u8=，u5+w58=6+6=12，即即 u5+w58 u8 修改临时标号修改临时标号u6=10，6=5，u7=9，7=5，u8=12，8=5，在所有在所有vjX4中，中，K=3+1=4 minu6，u7，u8，u9 =min10，9，12，=9=u7 点点v7得
13、永久标号，得永久标号，7=5，X2=v1，v4，v3，v2，v5，v7，X2=v6，v8，v9，在在vjX5中，临时标号不变。中，临时标号不变。K=4+1=5 minu6，u8，u9=min10，12，=10=u6 点点v6得永久标号，得永久标号，6=5，X6=v1，v4，v3，v2，v5，v7 ，v6，X6=v8，v9，点点v8，v9临时标号不变。临时标号不变。K=5+1=6 minu8，u9=min12，=12=u8 点点v8得永久标号，得永久标号，8=5，即从即从v1到到v8的最短路长为的最短路长为u8=12，8=5，5=2，2=3，3=1，知从知从v1到到v8 的最短路为：的最短路为：
14、P1，8=P（v1，v3，v2，v5，v8）v2v523464v3v1v4v6121061210v8v9v72363问题：本例中，问题：本例中，v1到到v9的最短路？的最短路？无向网络无向网络:负权弧时负权弧时。wijvivjwijwijvjvi无向网络中，最短路无向网络中，最短路最短链最短链。多个点对之间最短路？多个点对之间最短路？v1v2v312-3Dijkstra算法失效算法失效三、三、Ford算法算法算法思想：逐次逼近算法思想：逐次逼近每次逼近是求每次逼近是求D中从顶点中从顶点V1到其余各点的带有限制的最短路。到其余各点的带有限制的最短路。第一次：自顶点到vj由一条弧组成的路中找一条最
15、短的第二次：自顶点到vj由不多于两条弧组成的路中找一条最短的第m次：自顶点到vj由不多于m条弧组成的路中找一条最短的最多进行n-1次逼近定理：设网络D不含负回路，pj(m)是D的自顶点v1到顶点vj由不多于m条弧组成的路中长度最小者，w(pj(m)=uj(m)，j=2,3,n,则对于一切2 j n,有uj(1)uj(m)=w1jminuk(m-1)+wkj1 k n2 m n-1算法步骤：算法步骤：令 l(v1)=0,l(vj)=1(2 j n);m=1,u1(m)=0，uj(m)=w1j (2 j n)。步骤0步骤2 若m+1=n-1，结束。若m+1n-1，置m=m+1，转步骤，转步骤1 步
16、骤1 对于一切2 j n，计算minuk(m)+wkj1 k n。设minuk(m)+wkj1 k n=ur(m)+wrj令uj(m+1)=ur(m)+wrj及l(vj)=l(vj)r若r=j其它v1v4v5v3v22251-433l(v1)=0,l(vj)=1(j=2,3,4,5)3,5,1,0)1(5)1(4)1(3)1(2)1(1uuuuu1)(l ,1222)1(2)2(2uwuu3)(l ,1555)3(5)4(5uwuu5)(l ,6454)1(5)2(4uwuu3)(l ,1535)1(3)2(5uwuu1)(l ,1222)2(2)3(2uwuu2)(l ,3233)2(3)3
17、(3uwuu5)(l ,4454)2(5)3(4uwuu3)(l ,1535)2(3)3(5uwuu1)(l ,1222)3(2)4(2uwuu2)(l ,3333)3(3)4(3uwuu5)4(l ,254)3(5)4(4uwuu2)(l ,3323)1(2)2(3uwuu8.3最短路问题8.3.1最短路问题定义 如下图所示的单行线交通网，每弧旁的数字代表通过这条单行线所需要的费用。现在某人要从 vs出发，到达v5，求使费用最小的旅行路线。v1v5v4v3vs21527346355v216921定义:给定一个赋权有向图，即给了一个有向图G=（V，A，W），对每一个弧aij=(vi,vj)A，
18、相应地有权w（aij）=wij V1，又给定 G中的两个顶点vs ,vt。设 P是G 中从vs 到 vt的一条路，定义路 P的权是 P中所有弧的权之和，记为W(P)。最短路问题就是要在所有从vs 到vt 的路中，求一条权最小的路，即求一条从vs 到vt 的路P*，使 式中对G中所有从vs到vt的路P取最小，称P*是从vs到vt的最短路，记为P(vs ,vt)路P*的权称为从 vs到vt 的距离，记为d(vs ,vt)。)(min*)(PWPWp8.3.2最短路算法之一DijksTra算法基本思想：第一、最短路的子路还是最短路定理:对于弧的权大于零的有向网络G=（V，A，W），若 P是 G中的一
19、条最短路，则P 的子路也是最 短路。第二、设非负权网络D=（V，A，W）中，vs 到所有其它顶点的最短路长度按大小排列为 d0d1d2dn。假设d1de 已对应的最短路径分 别为 P1=P(vs,v1),P2=P(vs,v2)Pk=P(vs,vk)，并记 SK=vs,v1vk。则Pk 中弧的数目不大于K。第三、最短路的迭代计算公式定理 对于非负权有向网络G=（V，A，W）中，vs到所有其它顶点的最长度按大小排列为 d0d1d2dn，假设 P1=P(vs,v1),P2=P(vs,v2)Pk=P(vs,vk)已求出。并记 SK=vs,v1vk，则第k+1最短路 的路长dk+1 可以按式求得：KKS
20、VS1,min,iKKksiivSvSdd v vw v vDijksTra算法的步骤：第一步（初始化）令k=0,S(0)=vs(S是永久标号点的集合)，T(0)=vs,v1vn（T是临时标号点的集合）d(0)(vs)=0，d(0)(vi)=(d(vi)是vi点赋予的路长的初始标号，i=1,2,n)。(vi)=vs(vi)是(vi)点被赋予的vsvi路径的vi先驱 点号，resent=vs(resent用于表示最新获得永久标号 的顶点)。第二步 k=k+1 于对所有临时标号 ，计算如果 ，则 lvT 1min,kkllldvdvd resentw resent v，1kklldvdv()klv
21、resent第三步第三步若若vk 满足满足 则则resent=vk,，。若若k=n，则结束，否则转第二步。，则结束，否则转第二步。minlkklvTd vdv 1kkkSSv 1kkkTTv例例 用用DijksTra算法求下图的最短路算法求下图的最短路v1v5v4v3vs21527346355v216921最短路的算法步骤如下：第一轮 k=0 ，（），（）resent=vs 0sSv 012345,Tv v v v v 0id v 0sdv ivTssvv isvvivT第二轮 k=1 标号如图第三轮 k=2 标号如图第四轮 k=3 标号如图第五轮 k=4 标号如图 第六轮 k=5 标号如图
22、最后v4获得永久标号 算法结束。512345,sSv v v v v v8.3.3 最短路算法之二逐次逼近算法逐次逼近算法的基本步骤与思路如下：第一步：赋初值 k=1（k为迭代步骤）的含义为从v1点到vj点只含有一个弧的最短路的路长。为从v1点到vj点只含有一个弧的最短路的终点vj的前一个顶点号。111,jj(1)1jjwv vAdv vA(1)1jd(1)11jv(1)1j第二步：递推k=k+1递推关系如式所示：（wij 为弧 的权）同时，路径标号 如式所示。（，即vl 是 中vj 的前一个顶点号）()(1)11minkkjiijiddw1,jn,ijv v()1kj(1)()(1)111(
23、)(1)11kkkjjj(k)1jkkljjddvdd 11111minAkkjiijlljiddwdw()1kjp第三步：判断若对于 ,有 ，则算法结束。否则，进一步判断k是否为n-1，若是则说明网络存在负回路，否则转步骤二。jvV()(1)11kkjjddijw(1)1jd(2)1jd(3)1jd(4)1jd(5)1jd1v2v3v4v5v6v1v2v3v4v5v6v)1(1j1v1v1v1v1v1v)2(1j1v3v1v2v3v1v)3(1j1v3v1v2v3v4v)4(1j1v3v1v2v4v4v)5(1j1v3v例题v1v5v4v3vs21527346355v216921逐次逼近法的
24、例题的算法过程(表中空格为+)jiwijd1j(1)d1j(2)d1j(3)d1j(4)d1j(5)v1v2v3v4v5v6045000000542222-307555550269777012129901513131j(1)v1v1v1v1v1v11j(1)v13v1v2v3v11j(1)v1v3v1v2v341j(1)v1v3v1v2v4v41j(1)v13v1v2v4v4为了加快收敛速度，可以利用如下的递推关系：为了加快收敛速度，可以利用如下的递推关系：(1)11jjdw1,2,jn()()(1)111min min,minkkkjiijiijijijddwdw四、四、Floyd算法算法
25、网络网络G=（V，A，W），令），令D=(dij)n n，表示表示G中中vi到到vj的最短路的长度。的最短路的长度。iju 考虑考虑G中任意两点中任意两点vi，vj，如将，如将G中中vi，vj以外的点以外的点都删掉，得只剩都删掉，得只剩vi，vj的一个子网络的一个子网络G0，记，记否则当 A,ij(0)ijjivvwdwij为弧（为弧（vi，vj）的权。）的权。在在G0中加入中加入v1及及G中与中与vi，vj，v1相相关联的弧，得关联的弧，得G1，G1中中vi到到vj的最短路的最短路长记为长记为 ,则一定有则一定有(1)ijd(0)j1(0)1i(0)(1),min ddddijijvivjv
26、1wij 再在再在D1中加入中加入v2及及D中与中与vi，vj，v1，v2相关联的相关联的弧，得弧，得D2，D2中中vi到到vj的最短路长记为的最短路长记为 ，则有，则有(2)iju (1)2(1)2(1)(2)min jiijijuu,uu 递推，递推，D中中n个点逐个加入子网络，终得个点逐个加入子网络，终得D中中vi到到vj的最短路路长的最短路路长 (n)ijijuu 如果计算结果希望给出具体的最短路的路径，如果计算结果希望给出具体的最短路的路径，则构造路径矩阵则构造路径矩阵S=(sij)n n,sij表示表示vi到到vj的最短路的的最短路的第一条弧的终点第一条弧的终点。如。如 ，则从，则
27、从vi到到vj的最短路的最短路的第一条弧为（的第一条弧为（vi，vt），第二条弧为从），第二条弧为从vt到到vj的的最短路的第一条弧。最短路的第一条弧。tsij)n(Floyd算法步骤：算法步骤：第第1步：步：)1,2,.,;1,2,.,(,)(S UU(0)(0)(0)(0)njnijssijnnij 第第2步：计算步：计算)1,2,3,.,(S )1,2,3,.,(U)()()()(nk)s(nk)u(nnkijknnkijk 其中其中1)-k(j1)-(ik)1k(ij1)-k(1)-k(kj1)-k(ik)1(ij1)-k(ij)k(ij1(1)-k(ik1)-k(ij)(uu u s
28、 u ,uminu kkikk)k-kjkijuuu ssu当)(S )()(nnnijns ,)(Unn)n(ij(n)u第第3步：当步：当k=n时，时，)n(ijs是是vi到到 vj最短路第一条弧的终点。最短路第一条弧的终点。是是vi到到 vj最短路路长。最短路路长。niju例例 求如下网络中各点对间最短路的路长。求如下网络中各点对间最短路的路长。v2v52-344v3v1v4-2658解：解：0240842036050D(0)5432154321543215432154321S (0)用用U(0)的第一行、第的第一行、第一列来修正其余的一列来修正其余的uij，即，即作作(0)j1(0)1
29、i(0)(1),minddddijijmin ，4+5同时，在修正同时，在修正 处修改处修改(1)iju(0)1(1)ijiSS 54315431543215432154321S (1)0240842036050D(0)029408942036050D(1)5432154321543215432154321S (0)1)0(41)1(42 ss11与与v4到到v1的第的第一段一段弧相弧相同同用用U（1）的第二行、第二列修正其余的的第二行、第二列修正其余的uij，029408942036050D(1)5431154311543215432154321S (1)021594608942036021
30、150D(2)541143115432154321421S (2)vivjv1v22)1(12)2(13 ss2211与与v1到到v2的第一的第一段弧相段弧相同同021594608942036021150D(2)5411114311543215432124221S (2)用用U(2)第三行、第三列修正其余的第三行、第三列修正其余的iju021594608942036021150D(3)5411114311543215432124221S (3)5411114311543215432124221S (3)021594608942036021150D(3)用用U(3)第四行、第四列修正其余的第四行
31、、第四列修正其余的iju02672608942036021150D(4)5414311543215432124221S (4)4 4 4 4354451 ss02672608942036021150D(4)5444414311543215432124221S (4)用用U(4)第五行、第五列修正其余的第五行、第五列修正其余的iju0267260894200943530120850D(5)54444143115352221S (5)2)4(15513 ss2 5)4(35531 ss5255555从从v1到到v3的最短路长度的最短路长度 。8d (5)13从从v5到到v2的最短路长度的最短路长度
32、 7(5)52d0267260894200943530120850D(5)5444414311553555552522221S (5)路径路径：,s2513 v1到到v3的最短路路经为的最短路路经为:P13=P(v1,v2,v5,v4,v3)路径路径：,2,1,4512542552 sssv5到到v2的最短路路经为的最短路路经为:P52=P(v5,v4,v1,v2),s5)5(23,s4)5(53 3)5(43 sv1v2v5v4 v3v5v3v4v2v153436-412-2U(5)=000004538316-2372-1-13-41041-1S(5)=1234523333334523542
33、121211练习：求各点间练习：求各点间最短路径及长度最短路径及长度例例 2 某台机器可连续工作某台机器可连续工作4年，也可于每年末卖掉，年，也可于每年末卖掉，换一台新的。已知于各年初购置一台新机器的价格换一台新的。已知于各年初购置一台新机器的价格及不同役龄机器年末的处理价格如下表。新机器第及不同役龄机器年末的处理价格如下表。新机器第一年运行及维修费为一年运行及维修费为0.3万元，使用万元，使用1-3年后机器每年年后机器每年的运行及维修费用分别为的运行及维修费用分别为0.8，1.5，2.0万元。试确定万元。试确定该机器的最优更新策略，使该机器的最优更新策略，使4年内用于更换、购买及年内用于更换
34、、购买及运行维修的总费用为最省。运行维修的总费用为最省。j第一年第一年 第二年第二年 第三年第三年 第四年第四年年初购置价年初购置价使用使用j年的机器处理价年的机器处理价2.52.02.61.62.81.33.11.1解题思路解题思路：设：设v1v2v3v4v5为各年年初，为各年年初，vij(ij)为从为从i年使用到年使用到j年年例例 3 某公司在六个城市某公司在六个城市c1,c6中有分公司，从中有分公司，从ci到到cj的直接航程票价记在下述矩阵中的的直接航程票价记在下述矩阵中的(i,j)位置上。（位置上。（表示无直接航路），请帮助该公司设计一张任意两城表示无直接航路），请帮助该公司设计一张任
35、意两城市间的票价最便宜的路线表。市间的票价最便宜的路线表。0 50 40 25 1050 0 15 20 25 15 0 10 20 25 20 10 0 5510 25 25 55 0例例 4 已知有已知有6个村子，相互间道路的距离如下图示。个村子，相互间道路的距离如下图示。拟合建一所小学，已知拟合建一所小学，已知A处有小学生处有小学生50人，人，B处处40人，人，C处处60人，人，D处处20人，人，E处处70人，人，F处处90人，问人，问小学应建在哪一个村子，使学生上学最方便（原则小学应建在哪一个村子，使学生上学最方便（原则所有人走的总路程最短；尽可能公平。）。所有人走的总路程最短；尽可能公平。）。AFEDCB2781361364解题思路解题思路：先求出各点之间的最短路路长：先求出各点之间的最短路路长6种设置方法种设置方法中总走行最短的中总走行最短的 6种设置方法最种设置方法最长与最短的差最长与最短的差最小的。小的。
