我正在写一篇关于一些图形算法(在 CPM 中使用)的论文,我需要一些可以在 DAG 中找到所有关键路径的算法的名称。我看过 Floyd - Warshall 算法,我不知道它是否有助于找到 DAG 中的所有关键路径。如果关键路径和最长路径是同一件事,那么可以修改 Floyd-Warshall 算法,以在图中找到所有最长而不是最短路径。即使可以修改,有没有更好的方法来找到所有关键路径?
2 回答
对于找到一条关键路径,具有负权重的 Floyd-Warshall 明显不如以下民间传说 (?) 算法,该算法以线性时间计算每个顶点的最长路径的长度。
for vertices v in topological order (sinks before sources):
set longest-path(v) := the maximum of 0 and length(v->w) + longest-path(w) for all arcs v->w
Floyd--Warshall 版本将longest-path(v) := the maximum of -distance(v, w) for all vertices w
在计算distance
数组后设置。
要找到所有关键路径,请计算longest-path
数组,并仅保留那些弧v->w
,longest-path(v) = length(v->w) + longest-path(w)
使用递归枚举残差 DAG 中的所有路径。
这可以通过 Floyd Warshall 来完成,只需否定所有权重(因为它是 DAG,不会有任何负循环)。但是,Floyd Warshall 是O(n^3)
,而存在更快的线性时间算法。
来自维基百科
加权图 G 中两个给定顶点 s 和 t 之间的最长路径与图 -G 中的最短路径相同,该最短路径是通过将每个权重变为其否定来从 G 导出的。因此,如果最短路径可以在 -G 中找到,那么最长路径也可以在 G 中找到。 [4] 对于大多数图,这种变换没有用,因为它在 -G 中创建了负长度的循环。但是,如果 G 是有向无环图,则不能创建负循环,并且可以通过对 -G 中的最短路径应用线性时间算法,在线性时间内找到 G 中的最长路径,这也是有向无环图。 4] 例如,对于给定 DAG 中的每个顶点 v,可以通过以下步骤获得以 v 为终点的最长路径的长度:
找到给定 DAG 的拓扑排序。对于 DAG 的每个顶点 v,在拓扑排序中,通过查看其传入邻居并将这些邻居记录的最大长度加一来计算以 v 结束的最长路径的长度。如果 v 没有传入邻居,则将结束于 v 的最长路径的长度设置为零。在任何一种情况下,都要记录这个数字,以便算法的后续步骤可以访问它。
一旦完成,整个 DAG 中最长的路径可以通过从记录值最大的顶点 v 开始,然后反复向后退到记录值最大的传入邻居,并反转在这边走。
请注意,找到所有最长的路径更成问题,因为它们的数量可能成倍增加。因此,没有最坏情况下有效的方法将它们全部列出,尽管它们可以很容易地被枚举或隐式表示。