存在比dijkstra更短的路径？

来源：9-2 Dijkstra算法的思想

天之子

2017-08-11

老师，在这张图中，如果0->3的距离是2.1，3到1的距离是0.1,那么经过0-3-1这条路径到达1的距离是2.2，比通过dijkstra算法求的的0-2-1的3还要小呢。我理解的是不是有问题啊？

写回答

2回答

慕雪9091725

2018-08-23

在你说的这种情况下

在结束了第一轮循环后

//img.mukewang.com/szimg/5b7e39200001cdbf05930333.jpg

0->并不会被更新为5 而是保持原来的2.1

所以下一轮可以确定0->3的最小值为2.1 同时0-3的这个2.1是所有结尾未作为源点路径中最短的

故0->3的最短路径可以确定为2.1 且下一轮循环将3作为源点继续

liuyubobobo

2017-08-11

抱歉，你说的是哪张图？

liuyubobobo

天之子

：）继续加油！

2017-08-12

共3条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 2

回答 2

回答 1