1、精选课件8.1 图的基本概念图的基本概念8.2 树树8.3 最短路问题最短路问题8.4 网络最大流问题网络最大流问题8.5 最小费用最大流问题最小费用最大流问题8.6 中国邮递员问题中国邮递员问题精选课件Page 3The Shortest-Path Problem精选课件Page 4 如何用最短的线路将三部电话连起来？如何用最短的线路将三部电话连起来？ 此问题可抽象为设此问题可抽象为设ABC为等边三角形，连接三顶点的为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如显然是二边之和（如ABAC）。）。
2、ABC8.3 最短路问题最短路问题精选课件Page 5ABCP但若增加一个周转站（新点但若增加一个周转站（新点P P），连接），连接4 4点的新网络的最短路点的新网络的最短路线为线为PAPBPC。最短新路径之长。最短新路径之长N比原来只连三点的最短比原来只连三点的最短路径要短。这样得到的网络不仅比原来节省材料，而且稳定路径要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。性也更好。8.3 最短路问题最短路问题精选课件Page 6 就是从给定的网络图中找出一点到各点或任意两点之间就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路距离最短的一条路 . . 有些问题，如选址、管
3、道铺设时的选线、设备更新、投有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。路的问题。因此这类问题在生产实际中得到广泛应用。8.3 最短路问题最短路问题精选课件Page 7定义定义 设连通图设连通图D=(V,A)，每一弧每一弧a= (vi,vj)，有一个非负权，有一个非负权 w(a)=wij (wij 0)如果如果P是D中从中从vs到到vt的一条路，称的一条路，称P中所有弧的权之和为路中所有弧的权之和为路P的权，记为的权，记为w(P)。0()m
4、in ()PPP 8.3 最短路问题最短路问题定义定义 设设D为有向赋权图，为有向赋权图，vs与与vt是是D中两点，在连接中两点，在连接vs与与vt的的所有路中，权最小的路所有路中，权最小的路P0称为从称为从vs到到vt的最短路。即的最短路。即最小的路最小的路P0的权称为从的权称为从vs到到vt的距离，记为的距离，记为(,)std v v(,)(,)sttsd v vd v v和不一定相等。 权值的意义是广泛的。可以表示距离，可以表示交通运权值的意义是广泛的。可以表示距离，可以表示交通运费，可以表示网络流量，在朋友关系图甚至可以表示友谊深费，可以表示网络流量，在朋友关系图甚至可以表示友谊深度。
5、但都可以抽象为距离。度。但都可以抽象为距离。精选课件Page 88.3 最短路问题最短路问题1、Dijkstra算法算法2、Floyd-Warshall算法算法 Dijkstra算法是典型的单源最短路径算法，用于计算一算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。中心向外层层扩展，直到扩展到终点为止。Dijkstra算法在算法在很多专业课程很多专业课程如数据结构，图论，运筹学等如数据结构，图论，运筹学等中都作为基本内中都作为基本内容有详细的介绍，。容有详细的介
6、绍，。 Floyd-Warshall算法是解决任意两点间的最短路径的算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。一种算法，可以正确处理有向图或负权的最短路径问题。注意该算法要求不存在负权边注意该算法要求不存在负权边精选课件Page 9迪杰斯特拉（迪杰斯特拉（1930-2002,1930-2002,荷兰人），早年钻研物理及数学，荷兰人），早年钻研物理及数学，转为计算学。转为计算学。19721972年获图灵奖（计算机界的诺贝尔奖）。年获图灵奖（计算机界的诺贝尔奖）。8.3 最短路问题最短路问题1959年，年， Dijkstra发现了在赋权图中求最短路的算法。发
7、现了在赋权图中求最短路的算法。1.提出提出“goto有害论有害论”; 2 .提出信号量和提出信号量和PV原语原语; 3.解决了解决了“哲学家聚餐哲学家聚餐”问题问题; 4.最短路径算法和银行家算法的创造者最短路径算法和银行家算法的创造者; 5.第一个第一个Algol 60编译器的设计者和实现者编译器的设计者和实现者; 6. THE操作系统的设计者和开发者操作系统的设计者和开发者; 与与D. E. Knuth并称为这个时代最伟大的计算机科学家的人。并称为这个时代最伟大的计算机科学家的人。 精选课件Page 10 若若P是从是从vs到到vt间的最短路间的最短路, vi是是P中的一个点中的一个点,则
8、则vs到到vi的最的最短路就是从短路就是从vs 沿沿P到到vi的那条路。的那条路。v1 v2 v3一定是一定是v1 v3的最短路，的最短路，v2 v3 v4也一定是也一定是v2 v4的最短路。的最短路。v1v2v3v4v58.3 最短路问题最短路问题一个最优策略的任一子策略也是最优策略一个最优策略的任一子策略也是最优策略. 精选课件Page 11 从从vs出发，给网络中的每个点对应记录一个数出发，给网络中的每个点对应记录一个数( (称为这称为这个点个点vi的标号的标号) )，它或者表示从，它或者表示从vs到该点到该点vi的最短路的权的最短路的权( (称称为为P标号标号, ,此为永久标号此为永久
9、标号) )，或者是从，或者是从vs到该点到该点vi的最短路的的最短路的权的上界权的上界( (称为称为T标号，此为临时标号标号，此为临时标号) )， 方法的每一步是去修改方法的每一步是去修改T标号，并且把某一个具标号，并且把某一个具T标号标号的点改变为具的点改变为具P标号的点，从而使标号的点，从而使D中具中具P标号的顶点数多标号的顶点数多一个，这样至多经过一个，这样至多经过p1 1步，当终点步，当终点vt得到标得到标号时号时，就可就可以求出从以求出从vs到各点的最短路。到各点的最短路。8.3 最短路问题最短路问题（1）基本思想：）基本思想：精选课件Page 12 P(v) ,T(v)分别表示点分
10、别表示点v的的P标号和标号和T标号，标号， Si表示第表示第i步时具步时具P标号点的集合。标号点的集合。 为了在求出从为了在求出从vs到各点的距离的同时，也求出从到各点的距离的同时，也求出从vs到各点的最到各点的最短路，给每个点短路，给每个点v以一个以一个值。算法终止时，值。算法终止时，若若( (v) )= =m，表示在从，表示在从vs到到v的最短路上，的最短路上，v的前一个点是的前一个点是v vm m；若若( (v)=)=M，表示，表示D中不含从中不含从vs到到v的路；的路；若若( (v)=)=0 0表示表示v= =vs。8.3 最短路问题最短路问题（2）标号含义：）标号含义：精选课件Pag
11、e 131v2v3v4v5v9v8v7v6v6231216410362342108.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标号的点。标号的点。精选课件Page 14 令令 dij 表示表示 vi 到到 vj 的直接
12、距离的直接距离(两点之间有边两点之间有边)，若两点之间，若两点之间没有边，则令没有边，则令 dij = ，若，若两点之间是有向边，则两点之间是有向边，则 dji = ；令令 dii = 0，s 表示始点，表示始点，t 表示终点表示终点（2）标号含义：）标号含义：精选课件Page 151.给始点给始点vs以以P标号标号 ，这表示从，这表示从vs到到 vs的最短距离的最短距离为为0，其余节点均给，其余节点均给T标号，标号， 。2.设节点设节点 vi 为刚得到为刚得到P标号的点，考虑点标号的点，考虑点vj，其中，其中 ，且，且vj为为T标号。对标号。对vj的的T标号进行如下修改：标号进行如下修改：3
13、.比较与比较与vi相邻的所有具有相邻的所有具有T标号的节点，把最小者改为标号的节点，把最小者改为P标号，即：标号，即： 当存在两个以上最小者时，可同时改为当存在两个以上最小者时，可同时改为P标号。若全部节标号。若全部节点均为点均为P标号，则停止，否则用标号，则停止，否则用vk代替代替vi，返回步骤（，返回步骤（2）。）。()0sP v ()(2,3, )iP vin (,)ijvvE ()min (),()jjii jT vT vP vw()min ()kiP vT v 8.3 最短路问题最短路问题（3）算法步骤：）算法步骤：精选课件Page 168.3 最短路问题最短路问题3v3v8v7v2
14、v5v6v46234127123v12例例8.8 用用Dijkstra算法求下图从算法求下图从v1到到v8的最短路。的最短路。 精选课件Page 17 解解 :(1)首先给首先给v1以以P标号，给其余所有点标号，给其余所有点T T 标号。标号。11()0, ( )(2,3,8)()0;iP vT viv ，(2)22112()min (),()min, 033T vT vP vw2242()min (),T()3()1,P vT vvv ，8.3 最短路问题最短路问题44114()min (),()min, 077T vT vP vw3v3v8v7v2v5v6v46234127123v12精选
15、课件Page 1855225()min (),()min,325T vT vP vw8.3 最短路问题最短路问题33223()min (),()min, 336T vT vP vw53455()min (), (), ()5()2,P vT vT vT vv ，44114()min (),()min, 077T vT vP vw(3)3v3v8v7v2v5v6v46234127123v12精选课件Page 198.3 最短路问题最短路问题66556()min (),()min,538T vT vP vw34346()()min (), (), ()6P vP vT vT vT v34()2,
16、()5,vv33223()min (),()min, 336T vT vP vw44554()min (),()min7, 516T vT vP vw3v3v8v7v2v5v6v46234127123v12(4)精选课件Page 2077447()min (),()min, 6410T vT vP vw66786()min (), (), ()8()5,P vT vT vT vv ，8.3 最短路问题最短路问题66556()min (),()min,538T vT vP vw88338()min (),()min, 6612T vT vP vw3v3v8v7v2v5v6v46234127123
17、v12(5)精选课件Page 2188668()min (),()min12, 8210T vT vP vw778()min (), ()9P vT vT v ，8.3 最短路问题最短路问题77667()min (),()min10, 819T vT vP vw7()6,v 3v3v8v7v2v5v6v46234127123v12(6)精选课件Page 22故算法终止，反向追踪得故算法终止，反向追踪得v1到到v8最短路为：最短路为：12568vvvvv8.3 最短路问题最短路问题88()min ()10P vT v，88778()min (),()min10, 9210T vT vP vw8(
18、)6,v 12534768()0, ()1, ()2, ()2, ()5, ()6, ()5, ()6.vvvvvvvv3v3v8v7v2v5v6v46234127123v12(7)精选课件Page 238.3 最短路问题最短路问题3v3v8v7v2v5v6v46234127123v12035661089精选课件Page 24V1V2V3V4V5V6V7V8 P=0T=+T=+T=+T=+T=+T=+T=+P=T=3T=+T=7T=+T=+T=+T=+ T=6T=7P=T=5T=+T=+T=+ P=T=6T=6 T=8T=+T=+ P=T=6 T=8T=9T=12 P=T=8T=10T=10
19、P=T=9T=11再无其它再无其它T 标号，所以标号，所以 T(V8)=P(V8)=10; min L()=10P=T=10精选课件Page 251v2v3v4v5v9v8v7v6v6231216410362342108.3 最短路问题最短路问题例例8.6 用用Dijkstra算法求下图从算法求下图从v1 1到到v6 6的最短路。的最短路。 精选课件Page 26 解解:(1)1()0, ( )(2,3,9),iP vT vi (2)22112()min (),()min, 066T vT vP vw33113()min (),()min, 033T vT vP vw42344()min ()
20、, (), ()1, ()1,P vT vT vT vv 44114()min (),()min, 011T vT vP vw1()0,v 1v2v3v4v5v9v8v7v6v6231216410362342108.3 最短路问题最短路问题精选课件Page 2722112()min (),()min, 066T vT vP vw33113()min (),()min, 033T vT vP vw66446()min (),()min, 11011T vT vP vw32363()min (), (), ()3, ()1,P vT vT vT vv 1v2v3v4v5v9v8v7v6v62312
21、1641036234210(3)(4)22332()min (),()min6, 325T vT vP vw66446()min (),()min, 11011T vT vP vw2262()min (), ()5, ()3,P vT vT vv 8.3 最短路问题最短路问题精选课件Page 288.3 最短路问题最短路问题52225()min (),()min, 516T vT vP vw5565()min (), ()6, ()2,P vT vT vv 66446()min (),()min, 11011T vT vP vw1v2v3v4v5v9v8v7v6v623121641036234
22、210(5)66556()min (),()min11, 6410T vT vP vw88558()min (),()min, 6612T vT vP vw（6）76787()min (), (), ()9, ()5,P vT vT vT vv 77557()min (),()min, 639T vT vP vw精选课件Page 291v2v3v4v5v9v8v7v6v6231216410362342106686()min (), ()10, ()5,P vT vT vv 88778()min (),()min12, 9412T vT vP vw66556()min (),()min11, 6
23、410T vT vP vw(7)88778()min (),()min12, 9412T vT vP vw(8)888()min ()12, ()5,P vT vv 8.3 最短路问题最短路问题精选课件Page 30故算法终止，得反向追踪得故算法终止，得反向追踪得v1到到v8的最短路为：的最短路为：13258vvvvv99(), ().T vvM 8.3 最短路问题最短路问题143257689()0, ()1, ()1, ()3, ()2, ()5,()5, ()5, ().vvvvvvvvvM1v2v3v4v5v9v8v7v6v623121641036234210(9)精选课件Page 31
24、1v2v3v4v5v9v8v7v6v6231216410362342101v3v2v5v8v8.3 最短路问题最短路问题如图：如图：精选课件Page 322371845661341052759346828.3 最短路问题最短路问题例例8.9 用用Dijkstra算法求下图从算法求下图从1到到8的最短路。的最短路。 精选课件Page 33237184566134105275934682S=1, P1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1p4=1p1=08.3 最短路问题最短路问题S=1,4, P4=1精选课件Page 3423718456613
25、4105275934682min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2S=1,2,4, p2=2p1=0p4=1p2=28.3 最短路问题最短路问题精选课件Page 35237184566134105275934682S=1,2,4min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3S=1,2,4,6, P6=3p2=2p4=1p1=0p6=38.3 最短路问题最短路问题精选课件Page 36237184566134105275934682S=1,2,4,6min c23,c
26、25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3S=1,2,4,6,7, P7=3p2=2p4=1p1=0p6=3p7=38.3 最短路问题最短路问题精选课件Page 37237184566134105275934682S=1,2,4,6,7min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6S=1,2,4,5,6,7, P5=6p2=2p4=1p1=0p6=3p7=3p5=68.3 最短路问题最短路问题精选课件Page 38237184566134105275934682S=1,2,4,6,7mi
27、n c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8S=1,2,3,4,5,6,7, P3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=88.3 最短路问题最短路问题精选课件Page 39237184566134105275934682S=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10S=1,2,3,4,5,6,7,8, P8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=108.3 最短路问题最短路问题精选课件Page 40237184
28、566134105275934682S=1,2,3,4,6,7,81 1到到8 8的最短路径为的最短路径为11，4 4，7 7，5 5，88，长度为，长度为1010。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=108.3 最短路问题最短路问题精选课件Page 41由此看到，此方法不仅求出了从由此看到，此方法不仅求出了从v1 1 到到 v8 8 的最短路长，同时的最短路长，同时也求出了从也求出了从v1 1 到到 任意一点任意一点 的最短路长。将从的最短路长。将从v1 1 到任一点的到任一点的最短路权标在图上，即可求出从最短路权标在图上，即可求出从v1 1 到任一点的最短路线。本
29、到任一点的最短路线。本例中例中v1 1 到到 v8 8 的最短路线是：的最短路线是：8.3 最短路问题最短路问题v1 v2 v5 v6 v8 精选课件Page 42从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到该点的最到该点的最短路线及最短距离，因此可以将每个点标号，求出短路线及最短距离，因此可以将每个点标号，求出vs到任意到任意点的最短路线，如果某个点点的最短路线，如果某个点vj不能标号，说明不能标号，说明vs不可达不可达vj 。注：无向图最短路的求法只将上述步骤注：无向图最短路的求法只将上述步骤2 2将弧改成边即可。将弧改成边即可。8.3 最短路问题
30、最短路问题精选课件Page 43例例8.7 用用Dijkstra算法求下图从算法求下图从v1 1到到v6 6的最短路。的最短路。 v1v2v3v4v6v5352242421 解解 （1 1）首先给）首先给v1以以P标号，给其余所有点标号，给其余所有点T T标号。标号。1()0P v ()(2,3,6)iT vi （2）（3）22112()min (),()min, 033T vT vP vw33113()min (),()min, 055T vT vP vw232min (),T()()3T vvP v（4）33223()min (),()min5, 314T vT vP vw44224()m
31、in (),()min, 325T vT vP vw55225()min (),()min, 325T vT vP vw8.3 最短路问题最短路问题精选课件Page 44v1v2v3v4v6v5352242421（5）（6）55335()min (),()min5, 445T vT vP vw66446()min (),()min, 549T vT vP vw66556()min (),()min, 527T vT vP vw（7）（8）（9）（10）反向追踪得反向追踪得v1到到v6的最短路为：的最短路为：1256vvvv3453min (), (), ()()4T vT vT vP v454
32、5min (), ()()()5T vT vP vP v44224()min (),()min, 325T vT vP vw666min (), ()()7T vT vP v8.3 最短路问题最短路问题精选课件Page 45 作业：作业： P239 习题习题8.108.3 最短路问题最短路问题精选课件Page 46小结小结学习要点：学习要点： 1. 理解最短路问题的概念；理解最短路问题的概念； 2. 理解理解Dijkstra算法的思想算法的思想 3. 掌握掌握Dijkstra算法的步骤算法的步骤。Dijkstra算法、Prim算法和Kruskal算法都属于典型的贪心算法精选课件精选课件Page
33、 48最短路问题最短路问题一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。精选课件Page 49最短路问题最短路问题 定义： 1）人M（Man），狼W（Wolf）， 羊G（Goat）， 草H（Hay） 2） 点 vi 表示河岸的状态 3） 边 ek 表示由状态 vi 经一次渡河到状态 vj 4） 权边 ek 上的权定为 1我们可以得到下面的加权有向图我们可以得到下面的加权有向图精选课件Page 50最短路问题最短路问题 状态说明： v1,u1 =( M,W,G,H ); v2,u2 =(M,W,G); v3,u3 =(M,W,H); v4,u4=(M,G,H); v5,u5 =(M,G)此游戏转化为在下面的二部图中求从此游戏转化为在下面的二部图中求从 v1 到到 u1 的最短路问题。的最短路问题。v1v2v3v4v5u5u4u3u2u1精选课件
