在图中寻找最短路径的算法

Question

我刚看了这个视频：https://youtu.be/2E7MmKv0Y24?t=1335，它讲述了一种算法，可以找到有向无环图中源点和指定顶点间的最短距离：

1.将图按拓扑排序，并用其线性形式表示
2.初始化所有顶点为正无穷，除源点之外，它的值被初始化为0
3.从源点迭代到最右边的顶点。对于每个顶点 u，更新其所有邻居 v 的距离，使得(distance between source and v)和(distance between source and u)+(distance between u and v)两者中取小

在约22:00处，教授说该算法适用于具有负权边但不包含环的图，但我认为该算法适用于包含非负权环的图。我正确吗？

- TYeung

---

你能否将视频内容以文本形式放在这里，而不是发布视频？他在谈论什么算法？ - Zabuzard

Answer 1

..., 但我认为算法适用于包含非负循环的图。我是对的吗？

是的，你是对的。请参阅此帖子以获取更多信息。

另一个问题是为什么我需要先对数组进行拓扑排序？我为什么不能只循环遍历每个邻居并计算到它们的距离呢？

如果我理解正确，您不能只去下一个节点，因为可能存在使用其他节点首先到达该节点的更短路径（例如，到达节点的成本为5，并且有另一种使用两个节点到达节点的方式，使用成本为1 + 1 = 2；在这种情况下，如果您不首先进行排序，则会使用错误的路径）

- Tobias

Answer 2

我意识到我的想法显然是错误的。如果图中存在环，则无法进行拓扑排序。

- TYeung