有向图线性算法 [英] Directed graph linear algorithm

问题描述

我想知道使用动态规划在线性时间内计算顶点s与图形的其他每个顶点之间的最短路径长度的最佳方法。

I would like to know the best way to calculate the length of the shortest path between vertex s and every other vertex of the graph in linear time using dynamic programming.

图形为加权DAG。

推荐答案

您可以期望的是一种在边和顶点数量上呈线性的算法，即 O （| E | + | V |），也可以在负权重的情况下正常工作。

What you can hope for is an algorithm linear in the number of edges and vertices, i.e. O(|E| + |V|), which also works correctly in presence of negative weights.

这是通过首先计算拓扑来完成的

This is done by first computing a topological order and then 'exploring' the graph in the order given by this topological order.

一些表示法：我们称 d'（s，v） 从 s 到 v 和 d（u ，v）从 u 到 v 的弧的长度/权重（如果有）

Some notation: let's call d'(s,v) the shortest distance from s to v and d(u,v) the length/weight of the arc from u to v (if it exists).

然后，对于当前正在访问的节点v，从 s 到 v 是每个邻居 d'（s，u）+ d（u，v）的最小值< v 的code> u 。
原则上，这与Dijkstra的算法非常相似，不同之处在于我们已经知道遍历顶点的顺序。

Then, for a node v that is currently being visited, the shortest path from s to v is the minimum of d'(s,u)+d(u,v) for each in-neighbour u of v. In principle, this is very similar to Dijkstra's algorithm except that we already know in which order to traverse the vertices.

拓扑排序可确保所有 v 的邻居已经被访问过，因此不会再次更新。因此，无论何时访问节点，分配给它的距离都是从 s 到 v 的正确的最短路径。因此，对于每个 v ，您最终得到最短的sv路径。

The topological sorting ensures that all in-neighbours of v have already been visited and will not be updated again. So, whenever a node has been visited, the distance it is assigned is the correct shortest path from s to v. Therefore, you end up with a shortest s-v-path for each v.

完整的描述和实现可以作为在此处中找到，该链接链接到这些讲义。我不确定该DAG算法的算法思想最初在文献中发表过。

A full description and implementation can be found here, which links to these lecture notes. I'm not sure where the algorithmic idea for this DAG algorithm was originally published in the literature.

即使存在负权重/距离，该算法也适用于DAG

This algorithm works for DAGs, even in the presence of negative weights/distances.

虽然该算法的典型实现很可能不会使用动态编程来明确实现，但由于找到了最短路径的问题，因此仍可以这样解释。使用到 v 邻居的最短路径来计算节点 v 。
要进一步讨论这种算法是否/如何算作动态编程，请允许我参考这个问题。

While a typical implementation of this algorithm will most likely not be done using dynamic programming explicitly, it can still be interpreted as such since the problem of finding a shortest path to a node v is computed using the shortest paths to the in-neighbours of v. For further discussion on if/how this type of algorithm counts as dynamic programming, let me refer you to this question.

这篇关于有向图线性算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！