网络优化第5章最短路问题

网

络

优

化

NetworkOptimization/netopt清华大学数学科学系

谢金星办公室：理科楼2206#（电话：62787812）Email:jxie@/~jxie/courses/netopt清华大学课号：70420133第5章最短路问题(ShortestPathProblem)1可编辑ppt许多实际问题都可以转化为最短路问题

其有效算法经常在其它网络优化问题中作为子算法调用

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

假设在时段t,产品的生产量为xt,期末产品的库存为It(I0=0);用二进制变量yt表示在时段t工厂是否进行生产准备.假设费用均非负，则在最优解中，即可以证明：一定存在满足条件的最优解.可以只考虑3可编辑ppt单产品、无能力限制的批量问题记wij为第i时段生产量为时所导致的费用(包括生产准备费、生产费和库存费),即其中网络：从所有节点i到j(>i)连一条弧,弧上的权为wi,j-1,如T=4时：12345w11

w33

w22

w44

w34

w23

w12

w13

w24

w14

4可编辑ppt例5.3计划评审技术,即PERT(ProjectEvaluation&ReviewTechnique),又称网络计划技术或统筹法)大型复杂工程项目(Project)往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求,每一子项目需要一定的时间完成.PERT网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路(关键路线).工程上所谓的关键路线法(CPM:CriticalPathMethod)基本上也是计划评审技术的一部分.项目网络不含圈,其最长路问题和最短路问题都是可解的.(开始)AF(结束)566744513B

EDC5可编辑ppt最短路问题给定有向网络N，弧（i，j）对应的权又称为弧长（或费用）.对于其中的两个顶点s，t，以s为起点和t为终点的有向路称为s-t有向路，其所经过的所有弧上的权（或弧长、费用）之和称为该有向路的权（或弧长、费用）.所有s-t有向路中权(或弧长、费用)最小的一条称为s-t最短路.

对于有向网络中的一个圈，定义它的权为圈上所有前向弧上的权的和,减去圈上所有反向弧上的权.权为正的圈称为正圈;权为负的圈称为负圈;权为0的圈称为零圈.对一个有向圈，

它的权就是圈上所有弧上的权的和.本章的圈一般都是指有向圈,我们直接将正有向圈简称为“正圈”，

负有向圈简称为“负圈”，

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

7可编辑pptxij表示弧（i，j）是否位于s-t路上：当xij=1时，表示弧（i，j）位于s-t路上，当xij=0时，表示弧（i，j）不在s-t路上.

关联矩阵是全么模矩阵，因此0-1变量可以松弛为区间[0,1]中的实数不含负圈，变量直接松弛为所有非负实数思考：为什么xij可以不限定为{0，1}？最短路问题的数学描述8可编辑ppt5.2.1Bellman方程对偶问题为

根据互补松弛条件,当x和u分别为原问题和对偶问题的最优解时:9可编辑pptBellman方程当某弧(i,j)位于最短路上时，

即变量xij>0时,一定有

如果u为对偶问题最优解,易知u+c(c为任意实数)仍为最优解.不妨令us=0，则u的具体数值就可以唯一确定了.Bellman方程(最短路方程、动态规划基本方程)相当于对节点j赋予的一个实数值uj（通常称为

“标号”），在us=0时表示的正好是节点s到节点j的最短路的长度.一般情况下直接求解最短路方程是相当困难的.10可编辑ppt定理5.1对于只含正有向圈的连通有向网络，从起点s到任一顶点j都存在最短路，它们构成以起点s为根的树形图（称为最短路树（TreeofShortestPaths）或最短路树形图（ShortestPathArborescence）），最短路的长度可以由Bellman方程唯一确定.前一部分实际上是Bellman最优化原理的直接结果；后一部分中Bellman方程解的唯一性可以用反证法证明（略）最短路树（树形图）AF566744513BEDC11可编辑ppt如果将定理中的条件“只含正有向圈”改为“不含负有向圈”：上述最短路仍然存在；Bellman方程的解的唯一性可能不成立.起点s到顶点的最短路长度分别是us=u1=0，u2

=10，u3

=11但此时只要u3=

u2+111(us=u1=0)就可以满足Bellman方程.如us=u1=0，u2

=8，u3

=9等最短路树（树形图）123101-1s对于一般的网络，Bellman方程只是最短路长度必须满足的必要条件，而不是充分条件；对于只含正有向圈(或无圈)的连通有向网络，它才是充要条件.12可编辑ppt最短路算法-如果采用邻接表表示法，可首先计算各节点的入度；然后找入度为零者编号；去掉已编号节点及相关弧，同时修改相邻节点入度（只需扫描该去掉的节点的出弧）；依次类推。如果采用邻接矩阵表示法，可首先计算各节点的入度；然后找入度为零者编号；去掉已编号节点及相关弧，同时修改相邻节点入度（只需扫描该去掉的节点的对应行）；依次类推。5.2.2无圈网络引理5.1(拓扑排序,TopologicalOrdering)设有向图D不含有向圈,则D的顶点总可以重新编号,使得.

该算法自然可以用来判断有向图是否无圈图.

13可编辑ppt最短路算法-当网络是无圈时，这一最短路算法的复杂度为5.2.2无圈网络当采用递推计算求解上述方程时,每个顶点和每条弧均被考虑一次.这是求解最短路问题可能达到的最小的复杂度,因为任何算法都至少必须对每条弧考虑一次14可编辑ppt最短路算法–例例5.4计算如下网络(图5.4(a))中从节点A到所有其它节点的最短路.

EABCD1-25-1-1341ABCD1-11E-2E-2135415-13412计算过程:=0,=min{0+1}=1,=min{0+(-1)}=-1,=min{0+5,1+(-2),-1+3}=-1,=min{-1+1,-1+4}=0.15可编辑ppt最短路算法-算法通过不断修改这些标号，进行迭代计算.当算法结束时，距离标号表示的是从起点到该顶点的最短路长度.基本思想：对于V中每一个顶点j，赋予两个数值（通常称为“标号”）：一个是距离标号uj，记录的是从起点到该顶点的最短路长度的上界；另一个是前趋标号pred（j），记录的是当起点s到该顶点j的一条路长取到该上界时，该条路中顶点j前面的那个直接前趋（节点）.

迭代进行计算的过程中，所有顶点实际上被分成了两类：一类是离起点s较近的顶点，它们的距离标号表示的是从点s到该顶点的最短路长度，因此其标号不会在以后的迭代中再被改变（称为永久标号）；一类是离起点s较远的顶点，它们的距离标号表示的只是从点到该顶点的最短路长度的上界，因此其标号还可能会在以后的迭代中再被改变（称为临时标号）.

5.2.3正费用网络(Dijkstra,1959)

16可编辑ppt正费用网络（Dijkstra算法）STEP1.如果S=V,则uj为节点s到节点j的最短路路长(最短路可以通过数组pred所记录的信息反向追踪获得),结束.否则继续STEP2.STEP0.(初始化)令S=，=V，；对V中的顶点j(js)令初始距离标号.

STEP2.从中找到距离标号最小的节点i，把它从删除，加入S.对于所有从i出发的弧,若，则令.

转STEP1.17可编辑ppt正费用网络（Dijkstra算法）归纳法.算法开始时结论成立.设直到迭代的第k步，上述结论(1)(2)成立.pred(j)

pred(i)

i

j

sP1P2S中具有最小标号的顶点i可以移入S中，这不会破坏结论（1）.引理5.2在上述Dijkstra算法中,

（1）对于S中的任一顶点j，其距离标号uj是从起点s到该顶点j的最短路路长； （2）对于中的任一顶点j，其距离标号uj是从起点s出发，只经过S中的顶点到达顶点j的最短路路长.对于中的其它顶点k，修改标号，不会破坏结论（2）.18可编辑pptDijkstra算法-计算复杂性分析

对于节点寻找过程，第一次循环时需要n次比较操作，第二次循环时需要n-1次比较操作，…，依次类推.因此，节点寻找过程的复杂度为综上所述，该算法的复杂度为该算法的主要计算量在于STEP2循环（最多执行n次），它包括两个过程：节点寻找过程（从中找到距离标号最小的节点i）和距离修改过程（修改与节点i相邻的节点的距离标号）.

对于距离修改过程，注意到一个顶点只有当它与顶点i相邻时，其标号才可能变更，才需要修改标号.每次循环所需要修改标号的顶点个数最多为这一过程的整体效应相当于对每条弧进行一次检查，所以该过程的总计算复杂度为O（m）.

对于稠密网络，这是求解最短路问题可能达到的最小的复杂度,因为任何算法都至少必须对每条弧考虑一次.对于稀疏网络，利用各种形式的堆（Heap），其复杂度可以降为或等19可编辑ppt标号算法（LabelingAlgorithm）标号算法：目的就是在算法结束时将所有临时标号转变为永久标号.无圈网络的最短路算法，也可以看成是一种标号算法.标号设定算法（Label-SettingAlgorithm）：在通过迭代过程对标号进行逐步修正的过程中，每次迭代将一个顶点从临时标号集合中移入永久标号集合中.一般只能用来求解无圈网络和正费用网络的最短路问题.标号修正算法（Label-CorrectingAlgorithm）：每次迭代时并不一定将任何顶点标号从临时标号转变为永久标号，只是对临时标号进行一次修正，所有顶点标号仍然都是临时标号；只有在所有迭代终止时，所有顶点标号同时转变为永久标号.标号设定算法可以看成是标号修正算法的特例，因为在算法终止之前，任何永久标号都可以看成是一种特殊的临时标号.对于一般费用网络的最短路问题采用.20可编辑ppt一般费用网络：标号修正算法

(逐次逼近法，SuccessiveApproximation)5.3.1Bellman-Ford算法(Ford,1956)归纳法计算从起点到所有其它顶点的最短路:相当于迭代法解Bellman方程引理5.3在（5.11）~(5.13)中,临时标号是从起点s=1到顶点j且所经过的弧数不超过k条时的最短路路长.

k=1显然成立.假设对k成立,下面考虑k+1的情况.从起点s=1到顶点j且所经过的弧数不超过k+1条时的最短路有两种可能：只含有不超过k条弧；含有k+1条弧。21可编辑pptBellman-Ford算法的复杂度

对于不含负有向圈的网络，最短路中弧的条数不超过n-1条.

算法一定在n-1步迭代后收敛

算法的主要工作量是(5.13)式的循环迭代，对给定的k和j，只需检查节点j的所有入弧即可.所以，对给定的k，正好需要对网络中的每条弧检查一次.因此，算法的总复杂度为O（mn）.

如果迭代不收敛，即存在某个节点j使得<,则说明网络本来就含有负有向圈.

因此本算法也可以用于判断网络是否含有负有向圈，复杂度为O（mn）.

22可编辑pptBellman-Ford算法（例）123451253-4231234512-4323可编辑ppt算法的总复杂度为O(mn2C).

基本思想：逐步逼近，迭代求解最短路方程STEP0:令距离标号us

=0,前趋标号pred(s)=0;对所有其它节点j令uj为无穷大.STEP1:如果对所有的弧（i，j）有uj

ui

+wij，则结束，uj就是从起点s到节点j的最短路长，最短路可以通过前趋标号（pred）获得.否则进行下一步.整数权，每次迭代使得一个节点的距离标号至少减少1对每个节点的距离标号的修正次数不超过2nC次总迭代次数不会超过2n2C次每次迭代都对所有弧进行检查和判断,需要m次操作（不指明具体寻找弧的方法时）5.3.2一般的标号修正算法

24可编辑pptBellman-Ford算法是（一般）标号修正算法的特例经过k遍检查以后，节点j所获得的距离标号

uj表示从起点s=1到顶点j且所经过的弧数不超过k条时的最短路路长.在一般标号修正算法中，可以首先对所有弧给定一个顺序，然后依次检查每条弧（i，j）并且在必要时对uj进行修正(减少)；当所有弧均被检查一遍以后，再从第一条弧开始下一遍检查.这正是Bellman-Ford算法

25可编辑ppt改进的（一般）标号修正算法基本思想：用链表记录可能满足

uj

>ui+wij的弧的起点STEP0:令LIST={s},距离标号us

=0,前趋标号pred(s)=0;对所有其它节点j令uj为无穷大。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.这一算法的总复杂度为26可编辑ppt计算网络中所有节点之间的最短路：Bellman-Ford：O(nmn)=O(mn2)Floyd-Warshall算法基本思想：逐步逼近，迭代求解最短路方程:O(n3)5.3.3Floyd-Warshall算法

（1962)引理5.4在（5.14）~(5.16)中,临时标号是不通过k，k+1，…,n节点(i,j除外)时从节点i到节点j的最短路路长.归纳法k=1显然成立.假设对k成立,下面考虑k+1的情况.从起点i到j且不通过k+1,…,n节点的最短路有两种可能：(1)不经过k节点；(2)经过k节点。27可编辑pptFloyd-Warshall算法的复杂度

对于不含负有向圈的网络，最短路中弧的条数不超过n-1条.

算法一定在n步迭代后收敛

算法的主要工作量是(5.16)式的循环迭代(三重循环),算法的总复杂度为O（n3）.

如果迭代不收敛，即存在节点i,j使得<,则说明网络本来就含有负有向圈.因此本算法也可以用于判断网络是否含有负有向圈，复