关于Floyed算法中的中间顶点t的描述

Question

老师，您好，这里的红色箭头指向的描述更严格地说是不是应该是：每轮循环求解出中间经过顶点t（t可以取 [0, V-1]）的最短路径。但是您这样说也是合理的，此时t的取值范围是 [0…t]。谢谢老师！

Answer 1

liuyubobobo 2020-01-15 03:07:59

这句话怎么表述还真是一个问题。

说中间一定经过顶点 t，也不准确。因为，如果 dis[v][t] + dis[t][w] > dis[v][w] 的话，那么就不会经过顶点 t。但是，我们尝试了一下，看看经过顶点 t 能不能得到更好的解。如果能，就把经过 t 的路径纳入到解中了，如果不能，就扔掉了。

所以或许，更准确的说法是，在每轮循环（t 那重循环），我们都已经对从 v 到 w 的路径，“尝试”了经过 [0...t] 中的点，看能否找到更短的路径。

不过，通过你的表述，我相信其实你已经理解这个算法了：）

感谢提醒，继续加油！：）

• 提问者 苏子浩 #1

  非常感谢！

• 提问者 苏子浩 #2

  老师现在给出的描述更加准确。感谢老师分享！