我希望找到最小权重最大的路径。
例如,如果有两条路径,它们的权重分别为10->1->10和2->2->2,则第二条路径被认为比第一条更好,因为最小权重(2)大于第一条路径的最小权重(1)。
如果有人能够想出一种方法来实现这一点,或者只是指引我一些参考资料,那将非常有用 :)
编辑:似乎我忘记提到我正在尝试从一个特定的顶点到达另一个特定的顶点。这是非常重要的一点 :/
编辑2:正如下面一位用户指出的那样,边缘权重是非负的。
我正在复制this的答案,并添加算法正确性的证明:
我会使用Dijkstra的某种变体。我直接从维基百科上获取了下面的伪代码,只改变了5个小地方:
dist
重命名为width
(从第3行开始)width
初始化为-无穷大
(第3行)无穷大
(第8行)-无穷大
(第14行)1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 width[v] := -infinity ; // Unknown width function from
4 // source to v
5 previous[v] := undefined ; // Previous node in optimal path
6 end for // from source
7
8 width[source] := infinity ; // Width from source to source
9 Q := the set of all nodes in Graph ; // All nodes in the graph are
10 // unoptimized – thus are in Q
11 while Q is not empty: // The main loop
12 u := vertex in Q with largest width in width[] ; // Source node in first case
13 remove u from Q ;
14 if width[u] = -infinity:
15 break ; // all remaining vertices are
16 end if // inaccessible from source
17
18 for each neighbor v of u: // where v has not yet been
19 // removed from Q.
20 alt := max(width[v], min(width[u], width_between(u, v))) ;
21 if alt > width[v]: // Relax (u,v,a)
22 width[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q; // Reorder v in the Queue
25 end if
26 end for
27 end while
28 return width;
29 endfunction
(s, a) = 300
),那么没有比通过 (s, b)
更好地到达 b
的方法,因此你知道了 b
的最佳情况容量。你继续前往已知顶点集的最佳邻居,直到到达所有顶点。val[W] = max(val[W], min(val[V], width_between(V-W)))
归纳步骤:假设W是集合B中具有最大val[W]的顶点。 W从队列中出列,并设置为答案val[W]。
现在,我们需要证明每条S-W路径的宽度都小于或等于val[W]。这总是正确的,因为到达W的所有其他方式都会通过集合B中的其他顶点(称其为X)。
对于集合B中的所有其他顶点X,val[X] ≤ val[W]
因此,到达W的任何其他路径都将受到val[X]的限制,val[X]永远不会大于val[W]。
因此,val[W]的当前估计值是最优的,因此算法计算出所有顶点的正确值。
我不确定Prim算法在这里是否适用。看看这个反例:
V = {1, 2, 3, 4}
E = {(1, 2), (2, 3), (1, 4), (4, 2)}
weight function w:
w((1,2)) = .1,
w((2,3)) = .3
w((1,4)) = .2
w((4,2)) = .25
如果您使用 Prim 算法来找到从 1 到 3 的最大最小路径,从 1 开始会选择 1 --> 2 --> 3
这条路径,而经过 4 的路径将获得最大最小距离。
这个问题可以用BFS算法解决,不过你需要两个变种:
例如,如果I和J是相邻点,I具有值w1,它们之间的边的权重为w2,则J=min(w1, w2)。
例如,如果I和J是相邻点,I具有值w1,J具有值w2,它们之间的边的权重为w3,则如果min(w2, w3)>w1,则必须重新标记J并再次处理其所有邻居节点。
好的,回答自己的问题只是为了尝试一下我在发布这个问题之前制定的可能解决方案所得到的反馈:
每个节点存储一个“路径片段”,这是到目前为止它自己的整个路径。
0)将当前顶点设置为起始顶点
1)从该顶点生成所有路径片段,并将它们添加到优先队列中
2)从优先级队列的顶部取出片段,将当前顶点设置为该路径的终止顶点
3)如果当前顶点是目标顶点,则返回路径
4)转到步骤1
我不确定这是否会找到最佳路径,我认为第三步中的退出条件有点过于雄心壮志。但我想不到更好的退出条件,因为此算法不关闭顶点(顶点可以在任意数量的路径片段中引用),您不能等待所有顶点关闭(例如Dijkstra算法)
你仍然可以使用Dijkstra算法!
不要使用+,而是使用min()运算符。
此外,您需要将堆/优先队列定向,使最大的元素位于顶部。
类似这样的代码应该可以工作:(我可能错过了一些实现细节)
let pq = priority queue of <node, minimum edge>, sorted by min. edge descending
push (start, infinity) on queue
mark start as visited
while !queue.empty:
current = pq.top()
pq.pop()
for all neighbors of current.node:
if neighbor has not been visited
pq.decrease_key(neighbor, min(current.weight, edge.weight))
保证每当您到达一个节点时,您都会遵循最优路径(因为您按递减顺序找到所有可能性,并且通过添加边缘永远无法改进路径)
时间限制与Dijkstra的相同-O(Vlog(E))。
编辑:哦等等,这基本上就是您发布的内容。哈哈。