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

Question

算法如下:

The algorithm starts by topologically sorting the dag (see Section 22.4) to impose a linear ordering on the vertices. If the dag contains a path from vertex u to vertex v, then u precedes v in the topological sort. We make just one pass over the vertices in the topologically sorted order. As we process each vertex, we relax each edge that leaves the vertex.

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

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

Answer 1

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

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

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