algorithm - 在图上寻找最便宜的路径，成本由使用节点的最大权重决定

Question

我有一个图 G，它有一个起始节点 S 和一个结束节点 E。这个图的特别之处在于它不是边有成本，而是节点有成本。我想找到 S 和 E 之间的方式(一组节点，W)，使 max(W) 最小化。 (实际上，我对 W 不感兴趣，只对 max(W) 感兴趣)等价地，如果我删除所有成本大于 k 的节点，那么使 S 和 E 仍然连接的最小 k 是多少？

我有一个想法，但想知道它是否正确和最优。这是我当前的伪代码:

L := Priority Queue of nodes (minimum on top)
L.add(S, S.weight)

while (!L.empty) {
    X = L.poll()
    return X.weight if (X == G)
    mark X visited
    foreach (unvisited neighbour N of X, N not in L) {
        N.weight = max(N.weight, X.weight)
        L.add(N, N.weight)
    }
}

我认为这是最坏的情况 O(n log n)，其中 n 是节点数。

这里是我的具体问题(渗透)的一些细节，但我也对这个问题的一般算法感兴趣。节点权重随机均匀分布在 0 和给定的最大值之间。我的节点是分布在 R² 平面上的泊松分布，如果两个节点之间的距离小于给定常数，则两个节点之间存在一条边。可能有很多节点，因此它们是动态生成的(隐藏在伪代码的 foreach 中)。我的起始节点在 (0,0) 中，结束节点是距离 (0,0) 大于 R 的任何节点。

编辑:节点上的权重是 float 。

Answer 1

从一个空图开始，您可以使用 fast union/find data structure 以递增的权重顺序一次插入一个顶点(及其与现有邻居的边)维护连接组件的集合。这就像 Kruskal algorithm为了构建最小生成树，而不是一次添加一条边，对于您处理的每个顶点 v，您将组合 v 的所有邻居的组件。

您还可以跟踪哪两个组件包含起始顶点和结束顶点。 (最初 comp(S) = S 和 comp(E) = E；在每个并集运算之前，可以检查两个输入分量 X 和 Y 以查看其中一个是 comp(S) 还是 comp(E)，并且后者在 O(1) 时间内相应更新。)一旦这两个组件成为单个组件(即 comp(S) = comp(E))，您就停止了。刚刚添加的顶点是S和E之间路径上使任意顶点的最大权重最小的最大权重顶点。

[编辑:添加时间复杂度信息]

如果图包含 n 个顶点和 m 条边，则需要 O(n log n) 时间对顶点按权重排序。最多会有 m 个并集操作(因为每条边都可以用来组合两个组件)。如果使用简单的不相交集合数据结构，所有这些并集操作都可以在 O(m + n log n) 时间内完成，这将成为整体时间复杂度；如果还使用路径压缩，这将下降到 O(m A(n))，其中 A(n) 是极其缓慢地增长的反阿克曼函数，但总体时间复杂度与以前相比保持不变，因为初始排序占主导地位。

假设权重为整数，Pham Trung 的二分搜索方法将花费 O((n + m) log maxW) 时间，其中 maxW 是图中最重的顶点。在稀疏图上(其中 m = O(n))，这变为 O(n log maxW)，而我的变为 O(n log n)，因此如果 log(maxW) << log(n)，他的算法将击败我的算法(即如果所有权重都非常小)。如果他的算法在具有大权重但只有少量不同权重的图上调用，那么一种可能的优化是在 O(n log n) 时间内对权重进行排序，然后将它们全部替换他们的排名按排序顺序排列。