寻找路径的最大最小重量
https://stackoverflow.com/questions/873126
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我试图找出一个算法找到一个路径穿过一个向图。这不是一个传统路径，我不能找到任何引用什么这样做了。
我想找到的路径具有最大重量最小。
I.e。如果有两种途径与重量10->1->10和2->2->2然后第二径被认为是更好的比第一，因为最小重量(2)大于最小重量的第(1).
如果任何人都可以作出一种方法来这样做，或者只是指向我的方向一些参考材料，这将是非常有用的：)
编辑：:看来我忘了说了，我试图从一个具体的顶点到另一个特定的顶点。相当重要的一点有:/
EDIT2::作为下面有人指出的那样，我应该强调的是，边缘量都是不负。
其他提示
我正在复制 这 回答并添加还添加我的算法正确性证明：
我会使用一些变体 迪克斯特拉氏. 。我直接从维基百科获取了下面的伪代码，只改变了 5 个小东西：
- 更名
dist到width（从第3行开始） - 初始化每个
width到-infinity（第3行） - 将源的宽度初始化为
infinity（8号线） - 将完成标准设置为
-infinity（第 14 行） - 修改了更新函数和标志（第20+21行）
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）。那么，没有更好的方法可以到达 b 然后通过 (s, b), ，这样你就知道了最佳的情况容量 b. 。您继续前往已知顶点集的最佳邻居，直到到达所有顶点。
算法正确性证明：
在算法中的任何一点，都会有 2 组顶点 A 和 B. 。A 中的顶点将是已找到正确的最大最小容量路径的顶点。集合 B 有一些顶点我们还没有找到答案。
归纳假设:在任何一步，集合 A 中的所有顶点都具有到它们的最大最小容量路径的正确值。即，所有先前的迭代都是正确的。
基本情况的正确性:当集合A仅有顶点S时。那么 S 的值为无穷大，这是正确的。
在当前迭代中，我们设置
val[W] = max(val[W], min(val[V], width_ Between(V-W)))
感应步骤:假设W是集合B中val[W]最大的顶点。并且 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] 的当前估计是最佳的，因此算法计算所有顶点的正确值。
您也可以使用范式“的答案二进制搜索”。即，做在权重二进制搜索，检测用于每个重量w是否可以找到仅使用重量比w更大的边缘图中的一个路径。
有关，你可以（通过二进制搜索发现）最大w给出了答案。请注意，您只需要检查是否存在路径，所以只是一个O（| E |）广度优先/深度优先搜索，而不是最短路径。因此，它是O(|E|*log(max W))的一切，媲美的Dijkstra /克鲁斯卡/普里姆的O(|E|log |V|)（我不能立即看到这些的证明，也是如此）。
这可以使用 BFS 风格的算法来解决，但是您需要两种变体：
- 您无需将每个节点标记为“已访问”，而是使用到达该节点的路径上的最小权重对其进行标记。
例如，如果I和J是邻居，I的值为w1，它们之间的边的权重为w2，则J=min(w1,w2)。
- 如果到达值为 w1 的标记节点，如果分配新值 w2（且 w2>w1），则可能需要重新标记并再次处理它。这是确保您获得所有最小值中的最大值所必需的。
例如，如果 I 和 J 是邻居，I 的值为 w1，J 的值为 w2，它们之间的边的权重为 w3，那么如果 min(w2, w3) > w1 则必须标记 J 并处理它的所有邻居再次。
我不知道该普里姆将在这里工作。借此反：
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而来的路径，同时
好吧，这里回答我的问题只是尝试并获得一点反馈我对临时解决办法，我在这里发帖之前，制定出：
每个节点存储一个“路径片段”，这是其自身的整个路径为止。
0）设定电流顶点到起始顶点，点击 1）生成这个顶点的所有路径碎片，并将它们添加到优先级队列结果 2）取下顶部离开优先级队列的片段，和当前顶点设置为路径搜索的结束顶点 3）如果当前顶点为目标顶点，然后返回路径点击 4）转到1结果
我不知道这会虽然找到最好的路径，我觉得在第三步退出条件是有点雄心勃勃。我想不出更好的退出条件虽然，因为这种算法不关闭顶点（顶点可以在尽可能多的路径片段被引用，因为它喜欢的），你不能只是等待，直到所有顶点被关闭（如Dijkstra的对例如）
您仍然可以使用Dijkstra的！
除了使用+的，使用MIN（）运算符。结果 另外，你要定向堆/ priority_queue，使最重要的事情是在上面。
像这样的东西应该工作：（我可能错过了一些实施细节）
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））
编辑：哦，等等，这基本上是你发布的内容。 LOL。
