计算DAG中每个顶点的单源最短路径算法背后的直觉
该算法如下：
该算法首先对数据进行拓扑排序(参见第22.4节)，在顶点上强制线性排序。如果dag包含从顶点u到顶点v的路径，那么在拓扑排序中，u先于v。在拓扑排序的顺序中，我们只对顶点进行一次遍历。当我们处理每个顶点时，我们放松每一条离开顶点的边缘。
谁能告诉我背后的直觉吗？使用这种直觉，请告诉我们如何找到最长的路径，只要取取边权值，并运行算法。
我们不能使用Dijkstra的算法，因为边被允许有负权。
回答 3
Stack Overflow用户
发布于 2016-05-17 02:29:38
如果您已经知道到达顶点之前的所有顶点的最短路径，那么找到到达顶点的最短路径是很容易的。在DAG中找到一个顶点的最长路径是很容易的，如果您已经知道能够在它之前的所有顶点的最长路径。
按拓扑顺序处理顶点，可以确保到到达顶点时，已经处理了所有可以在顶点之前的顶点。
Dijkstra的算法对于包含圈的图是必要的，因为它们不能按拓扑排序。
Stack Overflow用户
发布于 2016-05-17 10:31:38
您的问题与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算法和Bellman算法.主要的区别在于Bellman算法对图中的任意权值计算SSSP，并能检测出图中的负权圈，而Dijkstra的算法可以与正权值一起工作。
有关更多细节，请参见最短路径。
Stack Overflow用户
发布于 2021-06-21 06:49:51
拓扑排序确保我们在从源旅行时首先选择节点，这将确保每个节点至少有一个可以从源到达的条件。
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();
}
}
}
}当我们设置distsrc = 0时，它将从那里开始，条件disnode != infinity将不允许除src之外的任何其他节点首先进入该条件。因为拓扑排序在src之前出现，所以src将被丢弃。
https://stackoverflow.com/questions/37253739
复制相似问题
腾讯云开发者
