在图算法中找到最短路径

2024-05-18 • 问答

我刚刚看过以下视频：https://youtu.be/2E7MmKv0Y24?t=1335
它讨论了一种算法，该算法可找到DAG中源与给定顶点之间的最短距离：

1。按拓扑顺序对图进行排序，并以线性形式表示图
  2.将除源之外的所有顶点初始化为无穷大，源被初始化为0
  3.从源迭代到最右边的顶点。对于每个顶点u，将其所有相邻v的距离更新为min（（源与v之间的距离，（源与u之间的距离）+（u与v之间的距离））

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

另一个问题是，为什么我需要先对图进行拓扑排序？为什么我不能仅遍历每个邻居并计算与他们的距离？

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

是的，您是对的。有关更多信息，请参见this post。

另一个问题是为什么我需要首先对数组进行拓扑排序？为什么我不能仅遍历每个邻居并计算与他们的距离？

如果我正确理解了这个问题，那么您就不能只去任何一个下一个节点，因为可能有一种更短的方法来首先使用另一个节点（例如，到达一个节点的成本为5，而到达该节点的另一种方法）一个使用两个节点的节点，其成本为1 +1 = 2；如果在这种情况下不进行优先排序，则会使用错误的路径）

我意识到我显然不正确。如果图形具有循环，则无法进行拓扑排序。