为 DAG 中的每个顶点计算单源最短路径的算法背后的直觉

Question

算法如下：

该算法首先对 dag 进行拓扑排序（参见第 22.4 节）以对顶点进行线性排序。如果 dag 包含从顶点 u 到顶点 v 的路径，则在拓扑排序中 u 在 v 之前。我们只对拓扑排序的顶点进行一次遍历。当我们处理每个顶点时，我们放松离开顶点的每条边。

有人能告诉我它背后的直觉吗？并且使用这种直觉请告诉我们如何找到最长路径只是否定边缘权重并运行算法

我们不能使用 Dijkstra 算法，因为允许边具有负权重。

Answer 1

如果您已经知道到它之前的所有顶点的最短路径，那么找到到一个顶点的最短路径很容易。如果您已经知道到达它之前的所有顶点的最长路径，那么在 DAG 中查找到某个顶点的最长路径很容易。

按拓扑顺序处理顶点可确保当您到达某个顶点时，您已经处理了它之前的所有顶点。

Dijkstra 算法对于可以包含环的图是必要的，因为它们不能进行拓扑排序。