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

Question

我有一个图 G，它有一个起始节点 S 和一个结束节点 E。这个图的特别之处在于它不是边有成本，而是节点有成本。我想找到 S 和 E 之间的方式（一组节点，W），使 max(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

这个问题可以用二分查找解决。

假设解决方案是x，从一开始，我们将使用BFS或DFS来发现图，只访问那些权重<= x的节点。所以，最后，如果 Start 和 End 相连，x 可以解决。我们可以通过应用二进制搜索找到 x 的最佳值。

伪代码

int min = min_value_of_all_node;
int max = max_value_of_all_node;
int result = max;
while(min<= max){
    int mid = (min + max)>>1;
    if(BFS(mid)){//Using Breadth first search to discover the graph.
       result = min(mid, result);
       max = mid - 1;
    }else{
       min = mid + 1;
    }
}
print result;

注意：我们只需要应用那些存在于图中的权重，所以这有助于将二分查找的时间复杂度降低到O(log n)，其中n是不同权重的数量

如果权重是浮动的，只需使用以下方法：

List<Double> listWeight ;//Sorted list of weights
int min = 0;
int max = listWeight.size() - 1;
int result = max;
while(min<= max){
    int mid = (min + max)>>1;
    if(BFS(listWeight.get(mid))){//Using Breadth first search to discover the graph.
       result = min(mid, result);
       max = mid - 1;
    }else{
       min = mid + 1;
    }
}
print listWeight.get(result);

Answer 2

从一个空图开始，您可以使用 fast union/find data structure to maintain the set of connected components. This is just like the Kruskal algorithm 构建最小生成树，而不是添加边，按权重递增的顺序一次插入一个顶点（及其与现有邻居的边）一次一个，对于您处理的每个顶点 v，您将组合 v 的邻居的 all 的组件。

您还可以跟踪哪两个组件包含起始顶点和结束顶点。（最初 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)，他的算法将击败我的算法（即如果所有权重都非常小）。如果他的算法在具有大权重但只有少量 distinct 权重的图上调用，那么一种可能的优化是在 O(n log n) 时间内对权重进行排序，然后将它们全部替换为排序后的排名。

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

Finding cheapest path on a graph, cost determined by max-weight of used nodes

algorithm

graph

graph-algorithm

path-finding