网络优化-第5章-最短路问题课件.ppt

1、1网网 络络 优优 化化 Network Optimizationhttp:/ 谢金星办公室：理科楼2206#（电话：62787812）Email: http:/ 5章章 最短路问题最短路问题(Shortest Path Problem)2 许多实际问题都可以转化为最短路问题 其有效算法经常在其它网络优化问题中作为子算法调用 S ST T最短路问题的例子和意义3例例5.1 5.1（Single-level Uncapacitated LotsizingSingle-level Uncapacitated Lotsizing）某工厂生产某种产品用以满足市场需求某工厂生产某种产品用以满足市场需求,

2、且已知在时段且已知在时段t t中的市中的市场需求为场需求为dt.在某时段在某时段t t,如果开工生产如果开工生产,则生产开工所需的生则生产开工所需的生产准备费为产准备费为st,单件产品的生产费为单件产品的生产费为ct.在某时段在某时段t t期末期末,如果有如果有产品库存产品库存,单件产品的库存费为单件产品的库存费为ht.假设初始库存为假设初始库存为0,0,不考虑不考虑能力限制能力限制,工厂应如何安排生产工厂应如何安排生产,可以保证按时满足生产可以保证按时满足生产,且且使总费用最小使总费用最小?（Wagner WhitinWagner Whitin，19581958）最短路问题的例子最短路问题的

3、例子 -单产品、无能力限制的批量问题 假设在时段假设在时段t t,产品的生产量为产品的生产量为xt ,期末产品的库存为期末产品的库存为It(I0=0);=0);用二进制变量用二进制变量yt表示在时段表示在时段t t工厂是否进行生产准备工厂是否进行生产准备.假设费用均非负，则在最优解中假设费用均非负，则在最优解中 ，即，即 00TIITttTttdx11可以证明：一定存在满足条件可以证明：一定存在满足条件 的最优解的最优解.)1(01TtxItt可以只考虑可以只考虑txTtttttdddddd11,04单产品、无能力限制的批量问题记记wij为第为第i时段生产量为时段生产量为 时所导致的费用时所导

4、致的费用(包括生产准备费、生产费和库存费包括生产准备费、生产费和库存费),即即其中其中网络：从所有节点网络：从所有节点i到到j(i)连一条弧连一条弧,弧上的权为弧上的权为wi,j-1,如如T=4时：时：1jitttiiiijIhxcswjiiidddx1jittdddI21)1(jti1 12 23 34 45 5w1111 w3333 w2222 w4444 w3434 w2323 w1212 w1313 w2424 w1414 5例例5.3 5.3 计划评审技术计划评审技术,即即PERT(Project Evaluation PERT(Project Evaluation&Review T

5、echnique),&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 3 3 B B E E D D C C 6最短路问题最短路问题给定有向网络给定有向网络N N，弧（，弧（i i，j j）对应的权又称为）对应的权又称为弧长弧长（或（或费用费用）.对于其中的两个顶点对于其

7、中的两个顶点s s，t t，以，以s s为起点和为起点和t t为终点的有向路称为为终点的有向路称为s-ts-t有向路有向路，其所经过的所有弧上的权（或弧长、费用）之和，其所经过的所有弧上的权（或弧长、费用）之和称为该有向路的权（或弧长、费用）称为该有向路的权（或弧长、费用）.所有所有s-ts-t有向路中权有向路中权(或弧长、费用或弧长、费用)最小的一条称为最小的一条称为s-ts-t最短路最短路.对于有向网络中的一个圈，定义它的权为圈上所有前向弧上的对于有向网络中的一个圈，定义它的权为圈上所有前向弧上的权的和权的和,减去圈上所有反向弧上的权减去圈上所有反向弧上的权.权为正的圈称为权为正的圈称为正

8、圈正圈;权为负的圈称为权为负的圈称为负圈负圈;权为权为0 0的圈称为的圈称为零圈零圈.对一个有向圈，对一个有向圈，它的权就是圈上所有弧上的权的和它的权就是圈上所有弧上的权的和.本章的本章的圈一般都是指有向圈圈一般都是指有向圈,我们直接将正有向圈简称为我们直接将正有向圈简称为“正圈正圈”，负有向圈简称为负有向圈简称为“负圈负圈”，零有向圈简称为零有向圈简称为“零圈零圈”,而而“无圈无圈”指的是不存在有向圈指的是不存在有向圈.s st t7无向网络无向网络上的最短路问题一般可以转化为有向网络上的问题上的最短路问题一般可以转化为有向网络上的问题.如果所有弧上的权全为非负（或非正）数，只需将无向图的如

9、果所有弧上的权全为非负（或非正）数，只需将无向图的一条边代之以两条对称的有向弧即可一条边代之以两条对称的有向弧即可.如果弧上的权有负有正，一般来说问题要复杂得多。如果弧上的权有负有正，一般来说问题要复杂得多。最短路问题最短路问题 两点说明两点说明最长路问题最长路问题可以转化为最短路问题，把弧上的费用反号即可可以转化为最短路问题，把弧上的费用反号即可.必须指出：目前为止，一切最短路算法都只对不含负有向圈必须指出：目前为止，一切最短路算法都只对不含负有向圈的网络有效的网络有效.对于含负有向圈的网络，最短路问题是对于含负有向圈的网络，最短路问题是NPNP困难的困难的.因此，本章中除非特别说明，一律假

10、定网络不包含负有向圈因此，本章中除非特别说明，一律假定网络不包含负有向圈.8xij表示弧（表示弧（i，j）是否位于）是否位于s-t路上：当路上：当xij=1时，表示弧（时，表示弧（i，j）位于位于s-t路上，当路上，当xij=0时，表示弧（时，表示弧（i，j）不在）不在s-t路上路上.关联矩阵是全么模矩阵，因此关联矩阵是全么模矩阵，因此0-10-1变量可以松弛为变量可以松弛为区间区间0,10,1中的实数中的实数 不含负圈不含负圈，变量直接松弛为所有非负实数，变量直接松弛为所有非负实数)3.5(.0)2.5(,0,1,1.)1.5(min),(:),(:),(ijAijjjiAjijijAjii

11、jijxtsitisixxtsxw思考：为什么思考：为什么xij 可以不限定为可以不限定为0，1？最短路问题的数学描述最短路问题的数学描述95.2.1 Bellman5.2.1 Bellman方程方程 对偶问题为)3.5(.0)2.5(,0,1,1.)1.5(min),(:),(:),(ijAijjjiAjijijAjiijijxtsitisixxtsxw)5.5(.),(,.)4.5()max(Ajiwuutsuuijijst根据互补松弛条件,当x和u分别为原问题和对偶问题的最优解时:)6.5(.),(,0)(Ajiwuuxijijij10BellmanBellman方程方程当某弧当某弧(i

12、,j)位于最短路上时，位于最短路上时，即变量即变量xij0时时,一定有一定有 如果u为对偶问题最优解,易知u+c(c为任意实数)仍为最优解.不妨令 us=0，则u的具体数值就可以唯一确定了.Bellman方程(最短路方程、动态规划基本方程)相当于对节点j赋予的一个实数值uj（通常称为“标号”），在us=0时表示的正好是节点s到节点j的最短路的长度.ijijwuu)8.5(.min)7.5(,0ijijijswuuu一般情况下直接求解最短路方程是相当困难的.11定理定理5.1 对于只含正有向圈的连通有向网络，从起点对于只含正有向圈的连通有向网络，从起点s到任一顶到任一顶点点j都存在最短路，它们构

13、成以起点都存在最短路，它们构成以起点s为根的树形图（称为为根的树形图（称为最短最短路树路树（Tree of Shortest Paths）或）或最短路树形图最短路树形图（Shortest Path Arborescence），最短路的长度可以由），最短路的长度可以由Bellman方程唯一确定方程唯一确定.前一部分实际上是前一部分实际上是BellmanBellman最优化原理的直接结果；最优化原理的直接结果；后一部分中后一部分中BellmanBellman方程解的唯一性可以用反证法证明（略）方程解的唯一性可以用反证法证明（略）最短路树（树形图）最短路树（树形图）A A F F 5 5 6 6 6

14、 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 12如果将定理中的条件如果将定理中的条件“只含正有向圈只含正有向圈”改为改为“不含负有向圈不含负有向圈”：上述最短路仍然存在；上述最短路仍然存在；BellmanBellman方程的解的唯一性可能不成立方程的解的唯一性可能不成立.起点s到顶点的最短路长度分别是us=u1=0，u2=10，u3=11但此时只要u3=u2+1 11(us=u1=0)就可以满足Bellman方程.如 us=u1=0，u2=8，u3=9 等最短路树（树形图）最短路树（树形图）1 12 23 310101 1-1-1s s对于一般的网络，

15、对于一般的网络，BellmanBellman方程只是最短路长度必须满足的方程只是最短路长度必须满足的必要必要条件条件，而不是充分条件；，而不是充分条件；对于只含正有向圈对于只含正有向圈(或无圈或无圈)的连通有向网络，它才是的连通有向网络，它才是充要条件充要条件.13最短路算法最短路算法 -如果采用邻接表表示法，可首先计算各节点的入度；如果采用邻接表表示法，可首先计算各节点的入度；然后找入度为零者编号；然后找入度为零者编号；去掉已编号节点及相关弧，同时修改相邻节点入度（只需扫描去掉已编号节点及相关弧，同时修改相邻节点入度（只需扫描该去掉的节点的出弧）；该去掉的节点的出弧）；依次类推。依次类推。如

16、果采用邻接矩阵表示法，可首先计算各节点的入度；如果采用邻接矩阵表示法，可首先计算各节点的入度；然后找入度为零者编号；然后找入度为零者编号；去掉已编号节点及相关弧，同时修改相邻节点入度（只需扫描去掉已编号节点及相关弧，同时修改相邻节点入度（只需扫描该去掉的节点的对应行）该去掉的节点的对应行）；依次类推。依次类推。5.2.2 5.2.2 无圈网络无圈网络 引理引理5.1(5.1(拓扑排序拓扑排序,Topological Ordering),Topological Ordering)设有向图设有向图D D不含不含有向圈有向圈,则则D D的顶点总可以重新编号的顶点总可以重新编号,使得使得 .Ajiji

17、),(,)(2nO)(2nO)(nO)(nO)(mO)(nmO)()(2nOnnO该算法自然可以用来判断有向图是否无圈图该算法自然可以用来判断有向图是否无圈图.)(mO14最短路算法最短路算法 -当网络是无圈时，这一最短路算法的复杂度为当网络是无圈时，这一最短路算法的复杂度为 5.2.2 5.2.2 无圈网络无圈网络 当采用递推计算求解上述方程时当采用递推计算求解上述方程时,每个顶点和每条弧每个顶点和每条弧均被考虑一次均被考虑一次 .)(nmO这是求解最短路问题可能达到的最小的复杂度这是求解最短路问题可能达到的最小的复杂度,因为因为任何算法都至少必须对每条弧考虑一次任何算法都至少必须对每条弧考

18、虑一次 )10.5(.min)9.5(,01ijijijswuuuu)()(mOnmO15最短路算法最短路算法 例例例例5.4 5.4 计算如下网络计算如下网络(图图5.4(5.4(a 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

19、-1+1,-1+4=0.1umin222iiiwuumin333iiiwuumin444iiiwuumin555iiiwuu16最短路算法最短路算法 -算法通过不断修改这些标号，进行迭代计算算法通过不断修改这些标号，进行迭代计算.当算法结束时，当算法结束时，距离标号表示的是从起点到该顶点的最短路长度距离标号表示的是从起点到该顶点的最短路长度.基本思想：对于基本思想：对于V V 中每一个顶点中每一个顶点j j，赋予两个数值（通常称为，赋予两个数值（通常称为“标号标号”）：）：一个是距离标号一个是距离标号uj ，记录的是从起点到该顶点的最短路长度的上界；，记录的是从起点到该顶点的最短路长度的上界；

20、另一个是前趋标号另一个是前趋标号predpred（j j），记录的是当起点），记录的是当起点s s到该顶点到该顶点j j 的一条路长取的一条路长取到该上界时，该条路中顶点到该上界时，该条路中顶点j j 前面的那个直接前趋（节点）前面的那个直接前趋（节点）.迭代进行计算的过程中，所有顶点实际上被分成了两类：迭代进行计算的过程中，所有顶点实际上被分成了两类：一类是离起点一类是离起点 s 较近的顶点，它们的距离标号表示的是从点较近的顶点，它们的距离标号表示的是从点s到到该顶点的最短路长度，因此其标号不会在以后的迭代中再被改该顶点的最短路长度，因此其标号不会在以后的迭代中再被改变（称为永久标号）；变（

21、称为永久标号）；一类是离起点一类是离起点 s 较远的顶点，它们的距离标号表示的只是从点较远的顶点，它们的距离标号表示的只是从点到该顶点的最短路长度的上界，因此其标号还可能会在以后的到该顶点的最短路长度的上界，因此其标号还可能会在以后的迭代中再被改变（称为临时标号）迭代中再被改变（称为临时标号）.5.2.3 正费用网络(Dijkstra,1959)17正费用网络（Dijkstra算法）STEP1.如果如果S=V,则则uj为节点为节点s到节点到节点j的最短路路长的最短路路长(最短路可最短路可以通过数组以通过数组pred所记录的信息反向追踪获得所记录的信息反向追踪获得),结束结束.否则继续否则继续S

22、TEP2.STEP0.(初始化)令S=，=V，；对V 中的顶点j(j s)令初始距离标号 .S0)(,01spreduusjuSTEP2.从从 中找到距离标号最小的节点中找到距离标号最小的节点i，把它从，把它从 删除，加删除，加入入S.对于所有从对于所有从i出发的弧出发的弧 ,若若 ，则令，则令 .转转STEP1.SSAji),(ijijwuuijpredwuuijij)(,18正费用网络（Dijkstra算法）归纳法归纳法.算法开始时结论成立算法开始时结论成立.设直到迭代的第设直到迭代的第k k步，上述结论步，上述结论(1)(2)(1)(2)成立成立.pred(jpred(j)pred(ip

23、red(i)i i j j s sP1P1P2P2S SS 中具有最小标号的顶点中具有最小标号的顶点 i 可以移入可以移入S中，这不会破坏结论（中，这不会破坏结论（1）.S引理引理5.2 5.2 在上述在上述DijkstraDijkstra 算法中算法中,（1 1）对于）对于S S中的任一顶点中的任一顶点j j，其距离标号，其距离标号uj是从起点是从起点s s到该顶点到该顶点j j 的的最短路路长；最短路路长；（2 2）对于）对于 中的任一顶点中的任一顶点j j，其距离标号，其距离标号uj是从起点是从起点s s出发，只经出发，只经过过S S中的顶点到达顶点中的顶点到达顶点j j 的最短路路长的

24、最短路路长.S对于对于 中的其它顶点中的其它顶点k k，修改标号，不会破坏结论（修改标号，不会破坏结论（2）.S19DijkstraDijkstra算法算法 -计算复杂性分析计算复杂性分析 对于节点寻找过程，第一次循环时需要对于节点寻找过程，第一次循环时需要n n次比较操作，第二次循环时需要次比较操作，第二次循环时需要n-1-1次比较操作，次比较操作，依次类推，依次类推.因此，节点寻找过程的复杂度为因此，节点寻找过程的复杂度为 综上所述，该算法的复杂度为综上所述，该算法的复杂度为 该该算法的主要计算量在于算法的主要计算量在于STEP2循环（最多执行循环（最多执行n次），它包括次），它包括两个过

25、程：节点寻找过程（从两个过程：节点寻找过程（从 中找到距离标号最小的节点中找到距离标号最小的节点i）和）和距离修改过程（修改与节点距离修改过程（修改与节点i相邻的节点的距离标号）相邻的节点的距离标号）.S)(1)1(2nOnn对于距离修改过程，注意到一个顶点只有当它与顶点对于距离修改过程，注意到一个顶点只有当它与顶点i i相邻时，其标号才可相邻时，其标号才可能变更，才需要修改标号能变更，才需要修改标号.每次循环所需要修改标号的顶点个数最多为每次循环所需要修改标号的顶点个数最多为这一过程的整体效应相当于对每条弧进行一次检查，所以该过程的总计算复这一过程的整体效应相当于对每条弧进行一次检查，所以该

26、过程的总计算复杂度为杂度为O（m）.)(id)()(22nOmnO对于稠密网络，这是求解最短路问题可能达到的最小的复杂度对于稠密网络，这是求解最短路问题可能达到的最小的复杂度,因为任何算因为任何算法都至少必须对每条弧考虑一次法都至少必须对每条弧考虑一次.对于稀疏网络，利用各种形式的堆（对于稀疏网络，利用各种形式的堆（HeapHeap），其复杂度可以降为），其复杂度可以降为 或或 等等)log(),log(nnmOnmO)log(CnmO20标号算法（标号算法（Labeling AlgorithmLabeling Algorithm）标号算法标号算法：目的就是在算法结束时将所有临时标号转变为永久

27、：目的就是在算法结束时将所有临时标号转变为永久标号标号.无圈网络的最短路算法，也可以看成是一种标号算法无圈网络的最短路算法，也可以看成是一种标号算法.标号设定算法（标号设定算法（Label-Setting AlgorithmLabel-Setting Algorithm）：在通过迭代：在通过迭代过程对标号进行逐步修正的过程中，每次迭代将一个顶点从临过程对标号进行逐步修正的过程中，每次迭代将一个顶点从临时标号集合中移入永久标号集合中时标号集合中移入永久标号集合中.一般只能用来求解一般只能用来求解无圈网络无圈网络和和正费用网络正费用网络的最短路问题的最短路问题.标号修正算法（标号修正算法（Labe

28、l-Correcting AlgorithmLabel-Correcting Algorithm）：每次迭代时：每次迭代时并不一定将任何顶点标号从临时标号转变为永久标号，只是对并不一定将任何顶点标号从临时标号转变为永久标号，只是对临时标号进行一次修正，所有顶点标号仍然都是临时标号；临时标号进行一次修正，所有顶点标号仍然都是临时标号；只有在所有迭代终止时，所有顶点标号同时转变为永久标号只有在所有迭代终止时，所有顶点标号同时转变为永久标号.标号设定算法可以看成是标号修正算法的特例，因为在算法终标号设定算法可以看成是标号修正算法的特例，因为在算法终止之前，任何永久标号都可以看成是一种特殊的临时标号止

29、之前，任何永久标号都可以看成是一种特殊的临时标号.对于对于一般费用网络一般费用网络的最短路问题采用的最短路问题采用.21一般费用网络：标号修正算法一般费用网络：标号修正算法 (逐次逼近法，逐次逼近法，Successive Approximation)Successive Approximation)5.3.1 Bellman-Ford5.3.1 Bellman-Ford算法算法 (Ford(Ford,19561956)归纳法归纳法计算从起点到所有其它顶点的最短路计算从起点到所有其它顶点的最短路:相当于迭代法解相当于迭代法解BellmanBellman方程方程)13.5(.1,21,min,mi

30、n)12.5(,1,)11.5(,0)()()1(1)1()1(1njnkwuuujwuuijkijikjkjjj引理引理5.3 在（在（5.11）(5.13)中中,临时标号临时标号 是从起点是从起点 s=1到顶点到顶点 j 且所经过的且所经过的弧数不超过弧数不超过 k 条时的最短路路长条时的最短路路长.)(kjuk=1显然成立显然成立.假设对假设对k成立成立,下面考虑下面考虑k+1 1的情况的情况.从起点从起点 s=1到顶点到顶点j 且所经过的弧数不超过且所经过的弧数不超过k+1条时的最短路有两种可能条时的最短路有两种可能：只含有不超过只含有不超过k条弧；条弧；含有含有k+1条弧。条弧。22

31、Bellman-FordBellman-Ford算法算法的复杂度的复杂度 对于不含负有向圈的网络，最短路中弧的条数不超过对于不含负有向圈的网络，最短路中弧的条数不超过n n-1-1条条.算法一定在算法一定在n n-1-1步迭代后收敛步迭代后收敛 算法的主要工作量是算法的主要工作量是(5.13)式的循环迭代，对给定的式的循环迭代，对给定的 k 和和 j，只，只需检查节点需检查节点 j 的所有入弧即可的所有入弧即可.所以，对给定的所以，对给定的k，正好需要对网，正好需要对网络中的每条弧检查一次络中的每条弧检查一次.因此，算法的总复杂度为因此，算法的总复杂度为O（mn）.)1(nju 如果迭代不收敛

32、，即存在某个节点如果迭代不收敛，即存在某个节点 j j 使得使得 ,iu+ijw的弧（i，j）,令ju=iu+ijw,pred(j)=i.转 STEP1.25Bellman-FordBellman-Ford算法是算法是（一般）标号修正算法的特例（一般）标号修正算法的特例经过经过k遍检查以后，节点遍检查以后，节点j所获得的距离标号所获得的距离标号 uj表示从起点表示从起点s=1到到顶点顶点j 且所经过的弧数不超过且所经过的弧数不超过k条时的最短路路长条时的最短路路长.在一般标号修正算法中，可以首先对所有弧给定一个顺序，然在一般标号修正算法中，可以首先对所有弧给定一个顺序，然后依次检查每条弧（后依

33、次检查每条弧（i，j）并且在必要时对）并且在必要时对uj进行修正进行修正(减少减少)；当所有弧均被检查一遍以后，再从第一条弧开始下一遍检查当所有弧均被检查一遍以后，再从第一条弧开始下一遍检查.这正是这正是Bellman-Ford算法算法 26改进的（一般）标号修正算法改进的（一般）标号修正算法基本思想：基本思想：用链表记录用链表记录可能可能满足满足 uj ui+wij的弧的起点的弧的起点STEP0:STEP0:令令LIST=LIST=s s,距离标号距离标号us =0,=0,前趋标号前趋标号predpred(s s)=0;)=0;对所对所有其它节点有其它节点j j令令uj为无穷大为无穷大。ST

34、EP1.STEP1.如果如果LIST=，则结束，则结束，uj 就是从起点就是从起点s到节点到节点j的最的最短路长，最短路可以通过前趋标号（短路长，最短路可以通过前趋标号（pred）回溯获得）回溯获得.否则进行否则进行下一步下一步.STEP2：从：从LIST中删去一个节点中删去一个节点i,对从对从i出发的每条弧（出发的每条弧（i，j）判断是否满足判断是否满足 uj ui+wij.如果是如果是,则令则令uj=ui+wij,pred(j)=i,并令并令LIST=LIST j.当从当从i出发的所有弧都检查完以后出发的所有弧都检查完以后,转转STEP1.这一算法的总复杂度为这一算法的总复杂度为 )()(

35、)2(mnCOidnCOi27计算网络中所有节点之间的最短路：计算网络中所有节点之间的最短路：Bellman-FordBellman-Ford：O(n mn)=O(mn2)Floyd-WarshallFloyd-Warshall算法基本思想：逐步逼近，迭代求解最短路算法基本思想：逐步逼近，迭代求解最短路方程方程:O(n3)5.3.3 Floyd-Warshall算法（1962)1962)16.5(.,1,min)15.5(,)14.5(,0)()()()1()1()1(nkjiuuuujiwuukkjkikkijkijijijii引理引理5.4 在（在（5.14）(5.16)中中,临时标号临时

36、标号 是不通过是不通过k，k+1，,n 节点节点(i,j 除外除外)时从节点时从节点i到节点到节点j的最短路路长的最短路路长.)(kiju归纳法归纳法k=1显然成立显然成立.假设对假设对k成立成立,下面考虑下面考虑k+1 1的情况的情况.从起点从起点i到到j 且且不通过不通过k+1,n 节点节点的最短路有两种可能的最短路有两种可能：(1)(1)不经过不经过k节点节点；(2)经过经过k节点节点。28Floyd-Warshall算法算法的复杂度的复杂度 对于不含负有向圈的网络，最短路中弧的条数不超过对于不含负有向圈的网络，最短路中弧的条数不超过n-1条条.算法一定在算法一定在n步迭代后收敛步迭代后

37、收敛 算法的主要工作量是算法的主要工作量是(5.16)式的循环迭代式的循环迭代(三重循环三重循环),),算法的总复算法的总复杂度为杂度为O（n3）.)1(niju 如果迭代不收敛，即存在节点如果迭代不收敛，即存在节点 i,j 使得使得 ,则说明网则说明网络本来就含有负有向圈络本来就含有负有向圈.)1(niju)2(niju因此本算法也可以用于判断网络是否含有负有向圈，复杂度因此本算法也可以用于判断网络是否含有负有向圈，复杂度为为O（n3）.在某次迭代在某次迭代k发现某个节点发现某个节点i使得使得 0,则说明网络本来就含有则说明网络本来就含有负有向圈负有向圈.)(kiiu29Floyd-Wars

38、hall算法算法的具体实现的具体实现 由于要记录所有节点之间最短路的信息由于要记录所有节点之间最短路的信息,所以这里我们要用一个二维数组所以这里我们要用一个二维数组P；可以依据二维数组可以依据二维数组P,采用采用“正向追踪正向追踪”的方式得到最短路的方式得到最短路.STEP2：如果：如果k=n,结束结束;否则转否则转STEP1.STEP0:k=0.对于所有节点对于所有节点i和和j:令令 ，,(，若节点，若节点i和和j之间没有弧之间没有弧,认为认为 ).jpij)1(0iiwijwijijwu)1(STEP1:k=k+1.对于所有节点对于所有节点i和和j:若若 ,令令 ,;否则令否则令 ,.)(

39、)()(kkjkikkijuuu)()1(kijkijpp)()1(kijkijuu)(,)1(kkikijpp)()()1(kkjkikkijuuu30Floyd-Warshall算法算法的例的例 1 12 23 34 44 4-3-3-3-36 65 510106 6-7-73 3,4321432143214321,06653010703340)1()1(PU31Floyd-Warshall算法算法的例的例 ,4121432143214321,02653010703340)2()2(PU,4222432243214321,016330107703340)3()3(PU32Floyd-Warshall算法算法的例的例 ,4222432233213321,01633010747030340)4()4(PU.4222434433213321,0163309647030340)5()5(PU终点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)33布 置 作 业目的掌握最短路的基本算法及复杂性分析内容网络优化网络优化第第140-143页页2；13；14；16 内容思考1；（不交）（不交）