在一个图中寻找最便宜的路径，其成本由使用节点的最大权重确定。

Question

我有一个图G，其中包含起始节点S和结束节点E。这个图的特殊之处在于，边不具有成本，而是节点具有成本。我想要找到连接S和E的路径（一组节点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的任意节点。

编辑：节点上的权重为浮点数。

- DrPhil

---

如果一个节点_N_有权重_w_，那么你可以将所有以_N_为终点的边赋予权重_w_。对于任何顶点这样做都会给你一个有向图，你可以在上面执行常规的图算法。事实上，考虑到您的真正目标，j_random_hacker的答案就是完美的方式 :) - Rerito

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) 时间内对权重进行排序，然后用它们在排序顺序中的排名替换它们。

- j_random_hacker

---

这是我问题的好解决方案。由于我的节点生成方式，它非常快速且易于实现。非常感谢！ - DrPhil

不客气 :) 我已经添加了一些关于最坏情况运行时间限制的信息。 - j_random_hacker

Answer 2

这个问题可以通过使用二分查找来解决。

假设解为x，从起点开始，我们将使用BFS或DFS来发现图形，仅访问具有权重<= x 的节点。因此，最终，如果起点和终点相连，则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);

- Pham Trung

---

据我所见，它似乎没有考虑不同的距离度量（最大而非总和）。 - amit

@amit，我明白了，我错误地理解了问题 :) - Pham Trung

@amit 我更新了我的答案 - Pham Trung

这看起来很有前途！不幸的是，权重是浮点数，而不是整数。二分查找应该仍然可行，但我必须使用 while(max - min > delta)，对吧？这个算法的复杂度将是 O(n log((max-min)/delta)) 吗？ - DrPhil

@DrPhil，您对于普通二分查找浮点数的方法是正确的，但是针对您的情况，我们可以用同样的方式处理整数。 - Pham Trung

@DrPhil 正如我在注释中所述，我们只需要关心图中存在的权重。更新了代码以证明这一点 :) - Pham Trung