8.3 最短路问题幻灯片

1、运 筹 学( Operations Research ),Chapter8 图与网络优化,8.1 图的基本概念 8.2 树 8.3 最短路问题 8.4 网络最大流问题 8.5 最小费用最大流问题 8.6 中国邮递员问题,本章主要内容：,8.3 最短路问题,The Shortest-Path Problem,如何用最短的线路将三部电话连起来？ 此问题可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如ABAC）。,A,B,C,8.3 最短路问题,A,B,C,P,但若增加一个周转站（新点P），连接4点的新网络的最短路线为PAPBPC。最短新

2、路径之长N比原来只连三点的最短路径要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。,8.3 最短路问题,最短路问题： 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 . 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,8.3 最短路问题,8.3.1 最短路问题,定义 设连通图D=(V,A)，每一弧a= (vi,vj)，有一个非负权 w(a)=wij (wij 0) 如果P是D中从vs到vt的一条路，称P中所有弧的权之和为路P的权，记为w(P)。,8.3 最短路问题,

3、定义 设D为有向赋权图，vs与vt是D中两点，在连接vs与vt的所有路中，权最小的路P0称为从vs到vt的最短路。即,最小的路P0的权称为从vs到vt的距离，记为,权值的意义是广泛的。可以表示距离，可以表示交通运费，可以表示网络流量，在朋友关系图甚至可以表示友谊深度。但都可以抽象为距离。,8.3 最短路问题,常见的最短路算法,1、Dijkstra算法,2、Floyd-Warshall算法,Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法在很多专业课程如数据结构，图论，运筹学等中

4、都作为基本内容有详细的介绍，。,Floyd-Warshall算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。,注意该算法要求不存在负权边,迪杰斯特拉（1930-2002,荷兰人），早年钻研物理及数学， 转为计算学。1972年获图灵奖（计算机界的诺贝尔奖）。,8.3 最短路问题,1959年， Dijkstra发现了在赋权图中求最短路的算法。,8.3.2 狄克斯特拉算法 (Dijkstra algorithm，也称双标号法）,1.提出“goto有害论”;,2 .提出信号量和PV原语;,3.解决了“哲学家聚餐”问题;,4.最短路径算法和银行家算法的创造者;,5.第一

5、个Algol 60编译器的设计者和实现者;,6. THE操作系统的设计者和开发者;,与D. E. Knuth并称为这个时代最伟大的计算机科学家的人。,若P是从vs到vt间的最短路, vi是P中的一个点,则vs到vi的最短路就是从vs 沿P到vi的那条路。,v1 v2 v3一定是v1 v3的最短路， v2 v3 v4也一定是v2 v4的最短路。,1、最短路算法基于以下原理：,8.3 最短路问题,一个最优策略的任一子策略也是最优策略.,从vs出发，给网络中的每个点对应记录一个数(称为这个点vi的标号)，它或者表示从vs到该点vi的最短路的权(称为P标号,此为永久标号)，或者是从vs到该点vi的最短

6、路的权的上界(称为T标号，此为临时标号)， 方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样至多经过p1步，当终点vt得到标号时，就可以求出从vs到各点的最短路。,2、Dijkstra算法,8.3 最短路问题,（1）基本思想：,P(v) ,T(v)分别表示点v的P标号和T标号， Si表示第i步时具P标号点的集合。 为了在求出从vs到各点的距离的同时，也求出从vs到各点的最短路，给每个点v以一个值。算法终止时， 若(v)=m，表示在从vs到v的最短路上，v的前一个点是vm； 若(v)=M，表示D中不含从vs到v的路； 若(v)=0表示

7、v=vs。,8.3 最短路问题,（2）标号含义：,8.3 最短路问题,s=1。d(v1，v1)=0。v1是具P标号的点。,现考查从v1发出的三条弧，(v1，v2)，(v1，v3)，和(v1，v4)。,mind(v1,v1)+12,d(v1,v1)+w13，d(v1,v1)+w14=d(v1,v1)+w14=1,所以从v1出发到v4所需的最小费用必定是1单位，,这样就可使v4变成具P标号的点。,令 dij 表示 vi 到 vj 的直接距离(两点之间有边)，若两点之间没有边，则令 dij = ，若两点之间是有向边，则 dji = ；令 dii = 0，s 表示始点，t 表示终点,（2）标号含义：,

8、1.给始点vs以P标号 ，这表示从vs到 vs的最短距离为0，其余节点均给T标号， 。 2.设节点 vi 为刚得到P标号的点，考虑点vj，其中 ，且vj为T标号。对vj的T标号进行如下修改： 3.比较与vi相邻的所有具有T标号的节点，把最小者改为P标号，即： 当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。,8.3 最短路问题,（3）算法步骤：,8.3 最短路问题,例8.8 用Dijkstra算法求下图从v1到v8的最短路。,解 :(1)首先给v1以P标号，给其余所有点T 标号。,(2),8.3 最短路问题,8.3 最短路问题,(3)

9、,8.3 最短路问题,(4),8.3 最短路问题,(5),8.3 最短路问题,(6),故算法终止，反向追踪得v1到v8最短路为：,8.3 最短路问题,(7),8.3 最短路问题,3,v3,v8,v7,v2,v5,v6,v4,6,2,3,4,1,2,7,1,2,3,v1,2,0,3,5,6,6,10,8,9,8.3 最短路问题,例8.6 用Dijkstra算法求下图从v1到v6的最短路。,解:(1),(2),8.3 最短路问题,(3),(4),8.3 最短路问题,8.3 最短路问题,(5),（6）,(7),(8),8.3 最短路问题,故算法终止，得反向追踪得v1到v8的最短路为：,8.3 最短路

10、问题,(9),8.3 最短路问题,如图：,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,8.3 最短路问题,例8.9 用Dijkstra算法求下图从1到8的最短路。,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,S=1, P1=0,min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1,p4=1,p1=0,8.3 最短路问题,S=1,4, P4=1,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,min c12,c16,c

11、42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 S=1,2,4, p2=2,p1=0,p4=1,p2=2,8.3 最短路问题,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,S=1,2,4,min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 S=1,2,4,6, P6=3,p2=2,p4=1,p1=0,p6=3,8.3 最短路问题,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,S=1,2,4,6,min c2

12、3,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 S=1,2,4,6,7, P7=3,p2=2,p4=1,p1=0,p6=3,p7=3,8.3 最短路问题,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,S=1,2,4,6,7,min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 S=1,2,4,5,6,7, P5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,8.3 最短路问题,2,3,7,1,8,4,5,6,6,1,3,4,1

13、0,5,2,7,5,9,3,4,6,8,2,S=1,2,4,6,7,min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 S=1,2,3,4,5,6,7, P3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,8.3 最短路问题,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,S=1,2,3,4,6,7,min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10 S=1,2,3,4,5,6,7,8, P8=10,p2=2,p4=

14、1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,8.3 最短路问题,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,S=1,2,3,4,6,7,8,1到8的最短路径为1，4，7，5，8，长度为10。,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,8.3 最短路问题,由此看到，此方法不仅求出了从v1 到 v8 的最短路长，同时也求出了从v1 到 任意一点 的最短路长。将从v1 到任一点的最短路权标在图上，即可求出从v1 到任一点的最短路线。本例中v1 到 v8 的最短路线是：,8.3 最短路问题,

15、v1 v2 v5 v6 v8,从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj 。,注：无向图最短路的求法只将上述步骤2将弧改成边即可。,8.3 最短路问题,例8.7 用Dijkstra算法求下图从v1到v6的最短路。,解 （1）首先给v1以P标号，给其余所有点T标号。,（2）,（3）,（4）,8.3 最短路问题,（5）,（6）,（7）,（8）,（9）,（10）,反向追踪得v1到v6的最短路为：,8.3 最短路问题,作业： P239 习题8.10,8.3 最短路问题,小结,学习要点： 1. 理解最短路问题的概念； 2. 理解Dijkstra算法的思想 3. 掌握Dijkstra算法的步骤。,Dijkstra算法、Prim算法和Kruskal算法都属于典型的贪心算法,The end,thank you!,最短路问题,例6.4 渡河游戏 一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。,最短路问题,定义： 1）人M（Man），狼W（Wolf）