在图表上查找最便宜的路径,成本由使用的节点的最大权重确定

Question

我有一个带有起始节点S和结束节点E的图G.这个图的特殊之处在于,不是边缘有成本,而是具有成本的节点.我想找到S和E之间的方式(一组节点,W),以便最小化(W).(实际上,我对W不感兴趣,只是max(W))等价,如果我删除成本大于k的所有节点,那么最小的k是什么,以便S和E仍然连接？

我有一个想法,但想知道它是否正确和最佳.这是我目前的伪代码:

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的距离上的任何节点.

编辑:节点上的权重是浮点数.

Answer 1

从空图开始，您可以按权重递增的顺序一次插入一个顶点（及其与现有邻居的边），使用快速并集/查找数据结构来维护一组连接的组件。这就像构建最小生成树的Kruskal 算法一样，但对于您处理的每个顶点 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) 时间内对权重进行排序，然后将它们全部替换为排序顺序中的排名。