algorithm - 在图算法中找到最短路径

Question

我刚刚看过这个视频:https://youtu.be/2E7MmKv0Y24?t=1335
它讨论了一种在 DAG 中找到源和给定顶点之间的最短距离的算法:

1.Sort the graph in topological order and express the graph in its linear form
2.Initialize all of the vertex to infinity except the source, which is initialized to 0
3.Iterate from the source to the rightmost vertex. For every vertex u, update the distance of all of its neighbor v to min((distance between source and v), (distance between source and u) + (distance between u and v))

大约在22:00，教授说这个算法适用于负边但图不能包含循环，但我认为该算法适用于包含非负循环的图。我说得对吗？

Answer 1

..., but i think the algorithm works for graphs that contain non-negative cycle. Am I right?

是的，你是对的。参见 this post获取更多信息。

Another question is why do I need to topologically sort the array first? Why can't I just loop through every neighbour and calculate the distance to them?

如果我正确理解了这个问题，你不能只去任何下一个节点，因为可能有一个更短的方式到这个节点首先使用另一个节点(例如，到达一个节点的成本是 5，还有另一种方式到使用成本为 1 + 1 = 2 的两个节点的节点；如果在这种情况下您不先排序，您将使用错误的路径)