1

我正在写一篇关于一些图形算法（在 CPM 中使用）的论文，我需要一些可以在 DAG 中找到所有关键路径的算法的名称。我看过 Floyd - Warshall 算法，我不知道它是否有助于找到 DAG 中的所有关键路径。如果关键路径和最长路径是同一件事，那么可以修改 Floyd-Warshall 算法，以在图中找到所有最长而不是最短路径。即使可以修改，有没有更好的方法来找到所有关键路径？

4

2 回答 2

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 中的所有路径。

于 2013-08-26T18:14:14.990 回答
1

这可以通过 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 开始，然后反复向后退到记录值最大的传入邻居，并反转在这边走。

请注意，找到所有最长的路径更成问题，因为它们的数量可能成倍增加。因此，没有最坏情况下有效的方法将它们全部列出，尽管它们可以很容易地被枚举或隐式表示。

于 2013-08-26T18:04:50.853 回答