在线性时间内找到有向图中边的最大成本差异的路径

Question

有一个有向图 G，其边具有正权重，我们将路径成本定义为具有最小权重和最大权重的边之间的差异。目标是在其他路径中找到成本最高的路径。我们不需要 return 路径本身只是最大成本。

如果x是顶点数，y是边数，那么x < 10^5和y < min(x^2,10^5)。限时1秒

根据边界我认为这个问题必须在 O(x+y) 时间内解决。

因此，根据问题属性和对其他算法的一些研究，我认为可能的答案可能包含多个 DFS（如 SCC 问题）。我还找到了一个 similar problem with Dijkstra's algorithm 可以针对这个问题进行修改，但我不太确定复杂性是否合适。还有一些其他问题与我的相似，但答案是 O(m^2) 或更高，效率不高。

除了上面提到的以外，我不知道如何解决这个问题，一些见解会很有帮助。谢谢

Answer 1

解决方法：由于我们的图表可以有循环，这使我们的事情变得复杂。让我们构建一个新图，在其中我们将所有 components of a strong connection“压缩”到一个顶点中，因此新图将是非循环的。在此过程中，让我们记住每个强连接组件的边的最大（maximumWeight[v]）和最小（minimumWeigh[v]）权重。我们花了 O(|V| + |E|) 时间，其中 |V| 是顶点数，|E| 是边数。

之后让我们在 O(|V|+|E|) 时间复杂度内制作给定图的 topological sorting。那我们来计算一下简单的DP。

dpMax[v] - 从该顶点到有路径的边的最大权重。 dpMin[v] - 从该顶点到有路径的边的最小权重。

默认值：如果顶点 v 是强连通分量，那么最大和最小权重已经在 maximumWeight[v] 和 minimumWeigh[v] 中计算，所以 dpMax[v] = maximumWeight[v] 和 dpMin[v] = minimumWeight[v]。否则 maximumWeight[v] = -Infinity 和 minimumWeigh[v] = Infinity.

按照拓扑顺序，让我们改进每个顶点的 DP：

int answer = -Infinity;
for(auto v : vertexesInTopologicalOrder) {
    int newMinDp = dpMin[v], newMaxDp = dpMax[v];
    for(auto e : v.outgoingEdges) {
        int l = dpMin[v];
        int r = dpMax[v];
        l = min(l, e.weight);
        r = max(r, e.weight);
        l = min(l, dpMin[e.target]);
        r = max(r, dpMax[e.target]);
        answer = max(answer, e.weight - l);
        answer = max(answer, r - e.weight);
        newMinDp = min(newMinDp, l);
        newMaxDp = max(newMaxDp, r);
    }
    dpMin[v] = newMinDp;
    dpMax[v] = newMaxDp;
}

由于我们按拓扑顺序计算DP，因此已经计算了可达到顶点的DP。

为了更好地理解，让我们看一个例子。

假设我们有这样一个初始图。

压缩后，图形将如下所示。

经过拓扑排序后，我们得到了这样的顶点顺序。（绿色数字）

依次计算所有DP值，同时更新答案。

最终答案6将在计算顶部顶点DP时得到。

我希望它非常详细和清晰。最终时间复杂度为O(|V|+|E|).

在线性时间内找到有向图中边的最大成本差异的路径

Find path with maximum cost difference of edges in directed graph in linear-time

algorithm

graph

graph-algorithm