algorithm - 将 Bellman-Ford 改进为线性运行时间

Question

在 Johnson 算法中，它使用 Bellman-Ford 将具有负边权重（无负循环）的图转换为具有相同最短路径但所有边权重均为非负的图 - 在 O(mn) 时间内。

假设我们有一个 DAG。我们如何使用另一种方法将 DAG 转换为具有相同最短路径的另一个图，但是在线性时间而不是之前的 O(mn) 时间。

我假设我们可以在执行 Johnson 算法期间修改 Bellman-Ford，但是我不确定如何使它成为线性的。本质上，我们如何找到一种方法来重新加权图中的所有边，使其在线性 O(n) 时间内为非负值？

标签： algorithmgraphcomputer-sciencegraph-algorithm