存在比dijkstra更短的路径？

Question

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

Answer 1

慕雪9091725 2018-08-23 12:37:54

在你说的这种情况下

在结束了第一轮循环后

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

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

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

Answer 2

liuyubobobo 2017-08-11 12:14:15

抱歉，你说的是哪张图？

• 提问者 天之子 #1

  哦哦，是9.2小节的那张图~

• 提问者 天之子 #2

  是我的问题，理解错了，这种情况下是不会选出0-2-1这条路径的。

• liuyubobobo 回复 提问者 天之子 #3

  ：） 继续加油！