在图上寻找最便宜的路径,成本由使用节点的最大权重决定
Finding cheapest path on a graph, cost determined by max-weight of used nodes
我有一个图 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 的任何节点。
编辑:节点上的权重是浮点数。
这个问题可以用二分查找解决。
假设解决方案是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);
从一个空图开始,您可以使用 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) 时间内对权重进行排序,然后将它们全部替换为排序后的排名。
我有一个图 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 的任何节点。
编辑:节点上的权重是浮点数。
这个问题可以用二分查找解决。
假设解决方案是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);
从一个空图开始,您可以使用 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) 时间内对权重进行排序,然后将它们全部替换为排序后的排名。