计算 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 算法对于可以包含循环的图是必需的，因为它们不能进行拓扑排序。

Answer 2

您的问题与 DAG 中的单源最短路径问题 (SSSP) 有关。图的拓扑排序表示图的线性排序。允许按拓扑顺序（从左到右）处理所有顶点，所有最短路径都将使用松弛属性找到。运行算法的时间是O(|V| + |E|)，其中V是一组顶点，E是一组边。

如果你想找到最长的路径（或关键路径），有以下变体：

第一种方法是对边权重取反。具有最小负值的路径将给出最长路径（但对于算法而言，它仍然是最小路径）。我们可以做到，因为拓扑排序可能适用于负边权重。

第二种方法是改变松弛步骤：

1. Cost of each vertex is initialized to negative infinity
2. Change the relaxation step:
  if d(v) < d(u) + w
  then d(v) = d(u) + w
  else d(v) is remains unchanged

where d - the distance;
u, v - vertices;
w - weight on edge (u, v).

一般情况下解决SSSP问题有Dijkstra's和Bellman-Ford算法。主要区别在于 Bellman-Ford 算法计算图中任意权重的 SSSP，并且可以检测图中的负权重循环，而 Dijkstra 算法可以处理正权重。

有关详细信息，请参阅 Shortest Paths。

Answer 3

拓扑排序确保我们在从源头移动时选择第一个到达的节点，这反过来将确保每个节点至少有一个条件可以从源头到达它。

for (int i = 0; i < N; i++)
    if (visited[i] == false)
        topologicalSortUtil(i, visited, stack, adj);

for (int i = 0; i < N; i++)
    dist[i] = Integer.MAX_VALUE;
dist[s] = 0;

while (stack.empty() == false)
{
    int node = (int)stack.pop();

    if (dist[node] != Integer.MAX_VALUE)
    {
        enter code here  for(Pair it: adj.get(node)) {
            if(dist[node] + it.getWeight() < dist[it.getV()]) {
                dist[it.getV()] = dist[node] + it.getWeight(); 
            }
        }
    }
}

由于我们设置dist[src] = 0，它将从那里开始，条件dis[node] != infinity 不会让除src 之外的任何其他节点首先进入该条件。因为在src之前的拓扑排序注释会被丢弃

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

Intuition behind the algorithm to compute single source shortest path for every vertex in DAG

algorithm

graph-theory

graph