《网络优化第5章最短路问题ppt课件》由会员分享，可在线阅读，更多相关《网络优化第5章最短路问题ppt课件（33页珍藏版）》请在金锄头文库上搜索。
1、网网 络络 优优 化化 Network Optimizationcsiam.edu/netopt清华大学数学科学系 谢金星办公室：文科楼2206# ：62787812:jxiemath.tsinghua.edu faculty.math.tsinghua.edu/jxie/courses/netopt清华大学课号：清华大学课号：70420213第第5 5章章 最短路问题最短路问题(Shortest Path (Shortest Path Problem)Problem) 许多实践问题都可以转化为最短路问题 其有效算法经常在其它网络优化问题中作为子算法调用 S ST T最短路问题的例子和意义例例
2、5.1 5.1 Single-level Uncapacitated LotsizingSingle-level Uncapacitated Lotsizing某工厂消某工厂消费某种某种产品用以品用以满足市足市场需求需求, ,且知在且知在时段段t t中的市中的市场需需求求为dt . dt . 在某在某时段段t, t, 假假设开工消开工消费, , 那么消那么消费开工所需的消开工所需的消费预备费为st , st , 单件件产品的消品的消费费为ct .ct .在某在某时段段t t期末期末, , 假假设有有产品品库存存, , 单件件产品的品的库存存费为ht . ht . 假假设初始初始库存存为0, 0
3、, 不思索不思索才干限制才干限制, , 工厂工厂应如何安排消如何安排消费, , 可以保可以保证按按时满足消足消费, , 且使且使总费用最小用最小? ? Wagner WhitinWagner Whitin，19581958最短路问题的例子最短路问题的例子 - - 单产品、无才干限制的批量问单产品、无才干限制的批量问题题 假假设在在时段段t, t, 产品的消品的消费量量为xt , xt , 期末期末产品的品的库存存为It (I0 It (I0 =0); =0); 用二用二进制制变量量ytyt表示在表示在时段段t t工厂能否工厂能否进展消展消费预备. . 假设费用均非负，那么在最优解中假设费用均非
4、负，那么在最优解中 ，即，即 可以证明：一定存在满足条件可以证明：一定存在满足条件 的最优解的最优解. .可以只思索可以只思索单产品、无才干限制的批量问题记记wijwij为第为第i i时段消费量为时段消费量为 时所导致的费用时所导致的费用( (包括消费预备费、消费费和库存费包括消费预备费、消费费和库存费), ), 即即其中其中网网络：从一切：从一切节点点i i到到j ( i)j ( i)连一条弧一条弧, , 弧上的弧上的权为wi,j-1 , wi,j-1 , 如如T=4T=4时：1 12 23 34 45 5w11 w33 w22 w44 w34 w23 w12 w13 w24 w14 例例5
5、.3 5.3 方案评审技术方案评审技术, , 即即PERT(Project Evaluation & PERT(Project Evaluation & Review Technique), Review Technique), 又称网络方案技术或统筹法又称网络方案技术或统筹法) )大型复大型复杂工程工程工程工程(Project)(Project)往往被分成往往被分成许多子工程多子工程, ,子工程之子工程之间有一定的先后有一定的先后顺序序( (偏序偏序) )要求要求, , 每一子工程需求一定的每一子工程需求一定的时间完成完成. PERT. PERT网网络的每条弧表示一个子工程的每条弧表示一个子
6、工程, ,假假设以弧以弧长表示每一子工表示每一子工程需求的程需求的时间, ,那么最早完工那么最早完工时间对应于网于网络中的最中的最长路路 ( (关关键道路道路). ). 工程上所工程上所谓的关的关键道路法道路法(CPM: Critical Path (CPM: Critical Path Method)Method)根本上也是方案根本上也是方案评审技技术的一部分的一部分. .工程网工程网络不含圈不含圈, , 其最其最长路路问题和最短路和最短路问题都是可解的都是可解的. . ( (开场开场) A ) A F ( F (终了终了) ) 5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1
7、 3 3 B B E E D D C C 最短路问题最短路问题给定有向网定有向网络N N，弧，弧i i，j j对应的的权又称又称为弧弧长或或费用用. . 对于其中的两个于其中的两个顶点点s s，t t，以，以s s为起点和起点和t t为终点的有向路称点的有向路称为s-ts-t有向路，其所有向路，其所经过的一切弧上的的一切弧上的权或弧或弧长、费用之和用之和称称为该有向路的有向路的权或弧或弧长、费用用. . 一切一切s-ts-t有向路中有向路中权( (或弧或弧长、费用用) )最小的一条称最小的一条称为s-ts-t最短路最短路. . 对于于有有向向网网络中中的的一一个个圈圈，定定义它它的的权为圈圈上
8、上一一切切前前向向弧弧上上的的权的的和和, , 减减去去圈圈上上一一切切反反向向弧弧上上的的权. . 权为正正的的圈圈称称为正正圈圈; ; 权为负的圈称的圈称为负圈圈; ; 权为0 0的圈称的圈称为零圈零圈. . 对一一个个有有向向圈圈， 它它的的权就就是是圈圈上上一一切切弧弧上上的的权的的和和. . 本本章章的的圈圈普普通通都都是是指指有有向向圈圈, , 我我们直直接接将将正正有有向向圈圈简称称为“正正圈圈， 负有有向向圈圈简称称为“负圈圈， 零零有有向向圈圈简称称为“零零圈圈, , 而而“无无圈圈指的是不存在有向圈指的是不存在有向圈. . s st t无向网无向网络上的最短路上的最短路问题
9、普通可以普通可以转化化为有向网有向网络上的上的问题. .假假设一一切切弧弧上上的的权全全为非非负或或非非正正数数，只只需需将将无无向向图的的一一条条边代之以两条代之以两条对称的有向弧即可称的有向弧即可. . 假假设弧上的弧上的权有有负有正，普通来有正，普通来说问题要复要复杂得多。得多。最短路最短路问题 两点两点阐明明最最长路路问题可以可以转化化为最短路最短路问题，把弧上的，把弧上的费用反号即可用反号即可. .必必需需指指出出：目目前前为止止，一一切切最最短短路路算算法法都都只只对不不含含负有有向向圈圈的的网网络有效有效. . 对于含于含负有向圈的网有向圈的网络，最短路，最短路问题是是NPNP困
10、困难的的. .因此，本章中除非特因此，本章中除非特别阐明，一概假定网明，一概假定网络不包含不包含负有向圈有向圈. . xij表示弧表示弧i，j能否位于能否位于s-t路上：当路上：当xij =1时，表示弧，表示弧i，j位于位于s-t路上，当路上，当xij =0时，表示弧，表示弧i，j不在不在s-t路上路上. 关关联矩矩阵是全么模矩是全么模矩阵，因此，因此0-10-1变量可以松弛量可以松弛为区区间0,10,1中的中的实数数 不含不含负圈，圈，变量直接松弛量直接松弛为一切非一切非负实数数思索：思索：为什么什么xij xij 可以不限定可以不限定为00，11？最短路问题的数学描画最短路问题的数学描画5
11、.2.1 Bellman5.2.1 Bellman方程方程 对偶问题为 根据互补松弛条件, 当x和u分别为原问题和对偶问题的最优解时: BellmanBellman方程方程当某弧当某弧(i,j)(i,j)位于最短路上位于最短路上时， 即即变量量xij0xij0时, , 一定有一定有 假设u为对偶问题最优解,易知u+c (c为恣意实数)仍为最优解. 无妨令 us=0 ，那么u的详细数值就可以独一确定了. Bellman方程(最短路方程、动态规划根本方程 ) 相当于对节点j赋予的一个实数值uj通常称为 “标号，在us=0时表示的正好是节点s到节点j的最短路的长度. 普通情况下直接求解最短路方程是相
12、当困难的. 定定理理5.1 5.1 对于于只只含含正正有有向向圈圈的的连通通有有向向网网络，从从起起点点s s到到任任一一顶点点j j都都存存在在最最短短路路，它它们构构成成以以起起点点s s为根根的的树形形图称称为最最短短路路树Tree Tree of of Shortest Shortest PathsPaths或或最最短短路路树形形图Shortest Shortest Path Path ArborescenceArborescence，最最短短路路的的长度度可可以以由由BellmanBellman方方程程独独一确定一确定. . 前一部分前一部分实践上是践上是BellmanBellman
13、最最优化原理的直接化原理的直接结果；果；后一部分中后一部分中BellmanBellman方程解的独一性可以用反方程解的独一性可以用反证法法证明略明略最短路树树形图最短路树树形图 A A F F 5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 假假设将定理中的条件将定理中的条件“只含正有向圈改只含正有向圈改为“不含不含负有向圈：有向圈：上述最短路依然存在；上述最短路依然存在；BellmanBellman方程的解的独一性能方程的解的独一性能够不成立不成立. . 起点s到顶点的最短路长度分别是us=u1=0， u2 =10， u3 =11但此时
14、只需u3 = u2+1 11 (us=u1=0)就可以满足Bellman方程. 如 us=u1=0， u2 =8， u3 =9 等最短路树树形图最短路树树形图 1 12 23 310101 1-1-1s s对于于普普通通的的网网络，BellmanBellman方方程程只只是是最最短短路路长度度必必需需满足足的的必必要要条件，而不是充分条件；条件，而不是充分条件； 对于只含正有向圈于只含正有向圈( (或无圈或无圈) )的的连通有向网通有向网络，它才是充要条件，它才是充要条件. . 最短路算法最短路算法 - -假假设采用采用邻接表表示法，可首先接表表示法，可首先计算各算各节点的入度；点的入度；然后
15、找入度然后找入度为零者零者编号；号；去掉已去掉已编号号节点及相关弧，同点及相关弧，同时修正相修正相邻节点入度只需点入度只需扫描描该去掉的去掉的节点的出弧；点的出弧；依次依次类推。推。假假设采用采用邻接矩接矩阵表示法，可首先表示法，可首先计算各算各节点的入度；点的入度；然后找入度然后找入度为零者零者编号；号；去掉已去掉已编号号节点及相关弧，同点及相关弧，同时修正相修正相邻节点入度只需点入度只需扫描描该去掉的去掉的节点的点的对应行行 ；依次依次类推。推。5.2.2 5.2.2 无圈网络无圈网络 引理引理5.1 (5.1 (拓扑排序拓扑排序, Topological Ordering) , Topo
16、logical Ordering) 设有向图设有向图D D不含不含有向圈有向圈, ,那么那么D D的顶点总可以重新编号的顶点总可以重新编号, ,使得使得 . . 该算法自然可以用来判算法自然可以用来判别有向有向图能否无圈能否无圈图. . 最短路算法最短路算法 - -当网当网络是无圈是无圈时，这一最短路算法的复一最短路算法的复杂度度为 5.2.2 5.2.2 无圈网络无圈网络 当采用当采用递推推计算求解上述方程算求解上述方程时, , 每个每个顶点和每条弧点和每条弧均被思索一次均被思索一次 . . 这是求解最短路是求解最短路问题能能够到达的最小的复到达的最小的复杂度度, , 由于由于任何算法都至少
17、必需任何算法都至少必需对每条弧思索一次每条弧思索一次 最短路算法最短路算法 例例例例5.4 5.4 计算如下网络计算如下网络( (图图5.4 (a)5.4 (a)中从节点中从节点A A到一切其它节点的最短路到一切其它节点的最短路. . E EA AB BC CD D1 1-2-25 5-1-1-1-13 34 41 1A AB BC CD D1 1-1-11 1E E-2-2E E-2-21 13 35 54 41 15 5-1-13 34 41 12 2计算过程:=0,=min0+1=1,=min0+(-1)=-1,=min0+5,1+(-2),-1+3=-1,=min-1+1,-1+4=0
18、.最短路算法最短路算法 - -算法算法经过不断修正不断修正这些些标号，号，进展迭代展迭代计算算. . 当算法当算法终了了时，间隔隔标号表示的是从起点到号表示的是从起点到该顶点的最短路点的最短路长度度. . 根本思想：根本思想：对于于V V 中每一个中每一个顶点点j j，赋予两个数予两个数值通常称通常称为“标号：号：一个是一个是间隔隔标号号uj uj ，记录的是从起点到的是从起点到该顶点的最短路点的最短路长度的上界；度的上界；另一个是前另一个是前趋标号号predpredj j，记录的是当起点的是当起点s s到到该顶点点j j 的一条路的一条路长取取到到该上界上界时，该条路中条路中顶点点j j 前
19、面的那个直接前前面的那个直接前趋节点点. . 迭代迭代进展展计算的算的过程中，一切程中，一切顶点点实践上被分成了两践上被分成了两类：一一类是离起点是离起点 s s 较近的近的顶点，它点，它们的的间隔隔标号表示的是从点号表示的是从点s s到到该顶点的最短路点的最短路长度，因此其度，因此其标号不会在以后的迭代中再被号不会在以后的迭代中再被改改动称称为永久永久标号；号；一一类是离起点是离起点 s s 较远的的顶点，它点，它们的的间隔隔标号表示的只是从点号表示的只是从点到到该顶点的最短路点的最短路长度的上界，因此其度的上界，因此其标号号还能能够会在以后的会在以后的迭代中再被改迭代中再被改动称称为暂时标
20、号号. . 5.2.3正费用网络(Dijkstra,1959)正费用网络Dijkstra算法STEP1. 假假设S=V, 那那么么uj为节点点s到到节点点j的的最最短短路路路路长(最最短短路路可可以以经过数数组pred所所记录的的信信息息反反向向追追踪踪获得得), 终了了. 否否那那么么继续STEP2. STEP0.(初始化)令S=，=V，；对V中的顶点j(js)令初始间隔标号.STEP2. 从从 中找到间隔标号最小的节点中找到间隔标号最小的节点i，把它从，把它从 删除，参与删除，参与S. 对于一切从对于一切从i出发的弧出发的弧 , 假设假设 ，那么令，那么令 . 转转STEP1. 正费用网络
21、Dijkstra算法归纳法法. . 算法开算法开场时结论成立成立. . 设直到迭代的第直到迭代的第k k步，上述步，上述结论(1)(2)(1)(2)成立成立. . pred(j) pred(j) pred(i) pred(i) i i j j s sP1P1P2P2S S 中具有最小标号的顶点中具有最小标号的顶点 i 可以移入可以移入S中，这不会破坏结论中，这不会破坏结论1. 引理引理5.2 在上述在上述Dijkstra 算法中算法中,1对对于于S中中的的任任一一顶顶点点j，其其间间隔隔标标号号uj是是从从起起点点s到到该该顶顶点点j 的的最短路路长；最短路路长；2对对于于 中中的的任任一一顶
22、顶点点j，其其间间隔隔标标号号uj是是从从起起点点s出出发发，只只经经过过S中的顶点到达顶点中的顶点到达顶点j 的最短路路长的最短路路长. 对于对于 中的其它顶点中的其它顶点k k， 修正标号，不会破坏结论修正标号，不会破坏结论2 2. . DijkstraDijkstra算法算法 - - 计算复杂性分析计算复杂性分析 对于于节点点寻觅过程程，第第一一次次循循环时需需求求n n次次比比较操操作作，第第二二次次循循环时需需求求n-1n-1次比次比较操作，操作，依次，依次类推推. . 因此，因此，节点点寻觅过程的复程的复杂度度为 综上所述，上所述，该算法的复算法的复杂度度为 该该算算法法的的主主要
23、要计计算算量量在在于于STEP2STEP2循循环环最最多多执执行行n n次次，它它包包括括两两个个过过程程：节节点点寻寻觅觅过过程程从从 中中找找到到间间隔隔标标号号最最小小的的节节点点i i和间隔修正正程修正与节点和间隔修正正程修正与节点i i相邻的节点的间隔标号相邻的节点的间隔标号. . 对对于于间间隔隔修修正正正正程程，留留意意到到一一个个顶顶点点只只需需当当它它与与顶顶点点i i相相邻邻时时，其其标标号号才才能能够变卦，才需求修正标号够变卦，才需求修正标号. . 每次循环所需求修正标号的顶点个数最多为每次循环所需求修正标号的顶点个数最多为这这一一过过程程的的整整体体效效应应相相当当于于
24、对对每每条条弧弧进进展展一一次次检检查查，所所以以该该过过程程的的总总计计算算复复杂度为杂度为O Om m. . 对对于于稠稠密密网网络络，这这是是求求解解最最短短路路问问题题能能够够到到达达的的最最小小的的复复杂杂度度, ,由由于于任任何何算算法都至少必需对每条弧思索一次法都至少必需对每条弧思索一次. .对于稀疏网络，利用各种方式的堆对于稀疏网络，利用各种方式的堆HeapHeap，其复杂度可以降为，其复杂度可以降为 或或 等等标号算法标号算法Labeling AlgorithmLabeling Algorithm 标号算法：目的就是在算法号算法：目的就是在算法终了了时将一切将一切暂时标号号转
25、变为永久永久标号号. . 无圈网无圈网络的最短路算法，也可以看成是一种的最短路算法，也可以看成是一种标号算法号算法. . 标号号设定算法定算法Label-Setting AlgorithmLabel-Setting Algorithm ：在：在经过迭代迭代过程程对标号号进展逐展逐渐修正的修正的过程中，每次迭代将一个程中，每次迭代将一个顶点从点从暂时标号集合中移入永久号集合中移入永久标号集合中号集合中. . 普通只能用来求解无圈网普通只能用来求解无圈网络和正和正费用网用网络的最短路的最短路问题. . 标号修正算法号修正算法Label-Correcting AlgorithmLabel-Corre
26、cting Algorithm：每次迭代：每次迭代时并不一定将任何并不一定将任何顶点点标号从号从暂时标号号转变为永久永久标号，只是号，只是对暂时标号号进展一次修正，一切展一次修正，一切顶点点标号依然都是号依然都是暂时标号；号；只需在一切迭代只需在一切迭代终止止时，一切，一切顶点点标号同号同时转变为永久永久标号号. . 标号号设定算法可以看成是定算法可以看成是标号修正算法的特例，由于在算法号修正算法的特例，由于在算法终止之前，任何永久止之前，任何永久标号都可以看成是一种特殊的号都可以看成是一种特殊的暂时标号号. . 对于普通于普通费用网用网络的最短路的最短路问题采用采用. . 普通费用网络：标号
27、修正算法普通费用网络：标号修正算法 ( (逐次逼近法，逐次逼近法，Successive Approximation)Successive Approximation)5.3.1 Bellman - Ford5.3.1 Bellman - Ford算法算法 (Ford,1956) (Ford,1956) 归纳法法计算从起点到一切其它算从起点到一切其它顶点的最短路点的最短路: : 相当于迭代法解相当于迭代法解BellmanBellman方程方程引引理理5.3 在在5.11(5.13)中中, 暂暂时时标标号号 是是从从起起点点 s =1到到顶顶点点 j 且且所所经经过过的弧数不超越的弧数不超越 k
28、条时的最短路路长条时的最短路路长. k=1显然成立然成立. 假假设对k成立成立,下面思索下面思索k+1的情况的情况.从起点从起点 s =1到到顶点点j 且所且所经过的弧数不超越的弧数不超越k+1条条时的最短路有两种能的最短路有两种能够： 只含有不超越只含有不超越k条弧；条弧； 含有含有k+1条弧。条弧。Bellman - FordBellman - Ford算法的复杂度算法的复杂度 对于不含于不含负有向圈的网有向圈的网络，最短路中弧的条数不超越，最短路中弧的条数不超越n-1n-1条条. . 算法一定在算法一定在n-1n-1步迭代后收步迭代后收敛 算算法法的的主主要要任任务量量是是(5.13)式
29、式的的循循环迭迭代代，对给定定的的 k 和和 j ，只只需需检查节点点 j 的的一一切切入入弧弧即即可可. 所所以以，对给定定的的k，正正好好需需求求对网网络中的每条弧中的每条弧检查一次一次. 因此，算法的因此，算法的总复复杂度度为Omn. 假假设设迭迭代代不不收收敛敛，即即存存在在某某个个节节点点 j j 使使得得 ui + wij的弧的起的弧的起点点STEP0: STEP0: 令令LIST=s,LIST=s,间隔隔标号号us us =0, =0, 前前趋标号号pred(s)=0;pred(s)=0;对一一切其它切其它节点点j j令令ujuj为无无穷大。大。STEP1. STEP1. 假假设
30、LIST= LIST= ，那那么么终了了， uj uj 就就是是从从起起点点s s到到节点点j j的的最最短短路路长，最最短短路路可可以以经过前前趋标号号predpred回回溯溯获得得. . 否否那那么么进展下一步展下一步. . STEP2：从从LIST中中删去去一一个个节点点i, 对从从i出出发的的每每条条弧弧i，j判判别能能否否满足足 uj ui + wij.假假设是是,那那么么令令uj = ui + wij, pred(j)=i, 并并令令LIST=LISTj. 当当从从i出出发的的一一切切弧弧都都检查完完以以后后,转STEP1.这一算法的一算法的总复复杂度度为 计算网算网络中一切中一切
31、节点之点之间的最短路：的最短路：Bellman-FordBellman-Ford：O(nO(nmn) = O(mn2)mn) = O(mn2)Floyd-WarshallFloyd-Warshall算算法法根根本本思思想想：逐逐渐逼逼近近，迭迭代代求求解解最最短短路路方方程程: O(n3): O(n3)5.3.3Floyd-Warshall算法1962)引引理理5.4 5.4 在在5.145.14(5.16)(5.16)中中, , 暂时标号号 是是不不经过k k，k+1k+1，,n ,n 节点点(i,j (i,j 除外除外) )时从从节点点i i到到节点点j j的最短路路的最短路路长. . 归
32、纳法法k=1显然成立然成立. 假假设对k成立成立,下面思索下面思索k+1的情况的情况.从起点从起点i到到j 且不且不经过k+1, n 节点的最短路有两种能点的最短路有两种能够： (1)不不经过k节点点 ； (2)经过k节点点 。Floyd-Warshall算法的复杂度 对于不含于不含负有向圈的网有向圈的网络，最短路中弧的条数不超越，最短路中弧的条数不超越n-1条条. 算法一定在算法一定在n步迭代后收步迭代后收敛 算算法法的的主主要要任任务量量是是(5.16)式式的的循循环迭迭代代(三三重重循循环),算算法法的的总复复杂度度为On3. 假假设设迭迭代代不不收收敛敛，即即存存在在节节点点 i,j
33、使使得得 ,那那么么阐阐明明网网络络本本来来就就含含有负有向圈有负有向圈. 因因此此本本算算法法也也可可以以用用于于判判别网网络能能否否含含有有负有有向向圈圈，复复杂度度为On3. 在在某某次次迭迭代代k发发现现某某个个节节点点i使使得得 0, 那那么么阐阐明明网网络络本本来来就就含含有负有向圈有负有向圈. Floyd-Warshall算法的详细实现由于要由于要记录一切一切节点之点之间最短路的信息最短路的信息, , 所以所以这里我里我们要用一个二要用一个二维数数组P P； 可以根据二可以根据二维数数组P, P, 采用采用“正向追踪的方式得到最短路正向追踪的方式得到最短路. . STEP2：假：
34、假设k=n, 终了了; 否那么否那么转STEP1. STEP0: k=0. 对于一切节点对于一切节点i和和j: 令令 ， , ( ，假设节点，假设节点i和和j之间没有弧之间没有弧, 以为以为 ) . STEP1: k=k+1. 对于一切节点对于一切节点i和和j: 假设假设 , 令令 , ; 否那么令否那么令 , . Floyd-Warshall算法的例1 12 23 34 44 4-3-3-3-36 65 510106 6-7-73 3Floyd-Warshall算法的例Floyd-Warshall算法的例终点1234起点1(1,2)(1,3)(1,3),(3,4)2(2,1)(2,3)(2,3),(3,4)3(3,4),(4,2),(2,1)(3,4),(4,2)(3,4)4(4,2),(2,1)(4,2)(4,2)(2,3)布置作业目的掌握最短路的根本算法及复杂性分析内容第第140-143页2；13；14；16 内容思索1 ； 不交不交
