【问题】《算法导论》上关于Dijkstra算法的一道练习题

2017/7/19镜像同步1 回复

看完算法导论中关于Dijkstra算法的讲解后，眼睛不小心扫到了一道练习题．．．想了半天没弄懂。题目是说有一个闲的蛋疼的教授觉得Dijkstra算法可以有一个更简单的证明方式，因为最短路径上每条边的松弛顺序与该条边在该条最短路中的次序相同，因此，路径松弛性质适用于源节点可以到达的所有节点。请构造一个有向图说明Dijkstra算法并不一定按照最短路径中边的出现次序来对边进行松弛。想了半天没想出反例。再从理论上考虑，假如对于某条最短路中的某条边u->v, 在对这条边进行松弛的时候，到u的最短路已经找到了啊，既然u->v在最短路中，那么src->...->u已经都松弛过了。如果找到了反例，或者我对题意理解有误，再或者是中文书的翻译有问题(我看的是中文第三版，题目是练习24.3-5),请告诉我(3Q).

订阅后，新回复会通过你的通知中心匿名送达。

1 条回复

NBAvictory机器人#1 · 2017/7/21

看了这个问题之后翻了一下手上的《算法导论》，然后思考了这个问题：假设起始结点s到结点t有路径且最短路径为s->...->x->y->...-)t，那么根据贪心策略，这些节点进入集合S的顺序一定是“...，x，y，...，t”了（假设不是这个顺序的话，比如y比x先进入集合S，这说明s到y的最短路径根本不需要经过x，s到t的最短路径就不会是s->...->x->y->...-)t了，跟你的思考是差不多的）。然后我查了一下答案（csdn上有“算法导论第三版教师手册（含习题答案）”），反例果然是在极端的条件下：存在几条权值为零的边，/叹息，权当是严谨性的体现吧。书上也赫然写着“该算法算法要求所有边的权重都为非负值”，嗯，是在下输了，学了几遍了都没注意过。