计算机问题求解 – 论题3-8 - 单源最短通路算法

Presentation on theme: "计算机问题求解 – 论题3-8 - 单源最短通路算法"— Presentation transcript:

1 计算机问题求解 – 论题3-8 - 单源最短通路算法
计算机问题求解 – 论题 单源最短通路算法 2018年10月30日

2 什么是最短通路问题? 问题1: 输入是什么?输出是什么？ Dijkstra算法为什么可能不是最小生成树？

3 问题2： 单源最短路问题的解必定是一棵树？ 所有节点都在源点s到某个节点的最短路径上 广度优先搜索树 由.π决定的最短路径树：

4 单源最短路问题具有最佳子结构性

5 简单的greedy策略不能正确解决最短通路 问题! 为什么？
1 6 s v 2 7 问题3： 简单的greedy策略不能正确解决最短通路 问题! 为什么？ 贪心选择策略出现了问题，不能保证贪心特性存在

6 问题4： 具有负值权的回路对于单源 最短通路问题的解有什么影 响？非负值权的回路呢？ 前者无解，定义为无穷小； 后者不影响

7 问题5： 在本章中介绍的算法基本 思路是一样的，那是什么？ 预估+修正=松弛 松弛+有序的松弛 效率的不断提高

8 “预估”与“修正” Relax用来描述v.d这个上限的紧缩过程。
Relax：v.d<=u.d+w(u,v)其实不容易得到保证：初始时v.d=无穷大，修正（松弛）时也只能保证当时满足。如果u.d变小了，该约束又可能不满足。 修正使得该条件越来越容易得到保证。如果v.d=&(s,v)以及u.d=&(s,u)，该约束无条件满足。

9 遍历顺序

10 问题6： Relax中的“修正”到底在 干什么？

11 当我们有u.d这么一个预估值后，v.d这个预估值必须小于u.d+w(u,v)(三角不等式),
s v u 当我们有u.d这么一个预估值后，v.d这个预估值必须小于u.d+w(u,v)(三角不等式), 如果relax时不小于，修正v.d为u.d+w(u,v) 修正后的v.d满足三角不等式的可能性大大提高 满足三角不等式的“压力”变小了

12 这是最短的路的权重 这是某条路径的权重而已 保证了修正一定是降低的v.d，至少不增。

13 v.d的上界特性 Never changes其实很重要，它保证了v.d一旦收敛到&，就不会再发生变化 既不会再减小，也不会增大

14 问题6： “修正”最终“可能”导致v.d=(s,v)。 但“可能”会变成“一定”吗？ 每次修正都是将预估值v.d缩小（最多不变）。
为什么一定能变成“一定”是理解算法的第一重点

15 假设s,…,u,v是s到v的一条最短路，算法执行某轮relax后有u.d= &(s,u) v.d>=&(s,v)(上界特性)
在下一轮relax(u,v)后,有v.d<=u.d+w(u,v)(类三角原理) u1 v.d=&(s,v) Sj Sj-1 u V S S2 S1 v.d<=u.d+w(u,v) =&(s,u)+w(u,v) =&(s,v) Um 其实，一旦v完成收敛，最短路已经形成,之后的relax已经无关

16 “一定”何时会发生

17 按照任意的次序做|V|-1次所有边的relax，一定让所有的v.d收敛？

18 其实，边数为k的最短路，第k次relax后就得到了！

19

20 Bellman-Ford算法的“部分”正确性
每轮relax中都对所有边进行 为什么？

21 只要没有源点可达的负权值回路，这个条件一定不会满足。只要有源点可达的负权值回路，这个条件一定会满足。

22 效率 这会影响什么？

23 问题7: Bellman-Ford算法的复 杂度是O(VE), 你是否觉 得relax操作太多了一些？ 有什么办法吗?
哪些边的relax是多余的？最短路径上已经收敛到&(s,v)的(u,v)边其实不用relax了。

24 换一种边的顺序，可能减少边的relax次数！

25 如果没有回路…

26 问题8： 为什么不需要做那么多次 relax操作了? 关键是被relax的边的顺序。

27

28 问题9： 没有回路的要求过高了， 有什么办法达到类似的效 果呢？

29 在V-S结点集合中，选择当前预估值最低的结点，放入S中。该点的d一定是&
问题10： 为什么这被认为是一个Greedy算法?

30 Dijkstra算法的正确性 用反证法证明关键的一步: 任一次特定循环, 即将加入S的顶点u必须满足 u.d = (s,u).
循环不变式: 用反证法证明关键的一步: 任一次特定循环, 即将加入S的顶点u必须满足 u.d = (s,u). u是第一个即将被加入S但不满足d=&的节点： 在左图的形势下(s到u的最短路), u.d既不能大 于y.d(否则不可能选u加入S), 也不能小于y.d (y.d=(s,y)<=&(s,u))。 因此，只能是u.d=y.d=(s,d)=&(s,u) 如果su最短路上还有Y-S节点，找到第一个y节点，x是y的直接前驱

31 问题11: Dijkstra算法对每条边最多relax 一次, 而且不要求输入是DAG, 它付出的代价是什么? 为什么必 须如此? 空间

32 问题12： 为什么说Dijkstra算法的复 杂度与其实现方法有关？ 显性或者隐性的优先队列操作
最小优先队列的三个基本操作：insert，extract-min，decrease-key(隐含在relax操作中)

33 问题13： 你能比较一下Dijkstra算法与 计算最小生成树的Prim算法 吗？Dijkstra算法的结果是否 一定是一个最小生成树？
非也！ Dijkstra算法得到一棵最短路径树；（相对于结点v0） 最短路径树是一个生成树，但未必最小（贪心的策略不一样）

34 Open Topics 请证明BF算法一定能够找到负权重环，请改造BF算法，输出负权重环；
请分析，如果用Fibonacci堆实现优先队列的话，Dijkstra算法时间复杂度为O（V*lgV + E）