有向无环图中计算每个顶点的单源最短路径算法背后的直觉

Question

算法如下：

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

有人能告诉我这背后的原理吗？并利用这种直觉告诉我们如何通过否定边缘权重并运行算法来找到最长路径

因为允许边缘具有负权重，所以无法使用Dijkstra算法。

- user4952610

Answer 1

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

按照拓扑排序处理顶点可以确保在到达某个顶点时，您已经处理完了所有可能在其前面的顶点。

Dijkstra算法用于包含环的图，因为它们无法进行拓扑排序。

- Matt Timmermans

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).

通常解决最短路径问题有迪杰斯特拉算法和贝尔曼-福德算法。主要区别在于贝尔曼-福德算法可以计算图中任意权重的最短路径，并且可以检测图中的负权重环，而迪杰斯特拉算法只能处理正权重。更多细节请参见最短路径。

- Didgeridoo

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 前面的节点将被丢弃。

- Manish