寻找具有最大最小权重的路径

Question

我正在尝试制定一种算法来查找有向图上的路径。 这不是一条传统的路径，我找不到任何类似的参考资料。

我想找到具有最大最小权重的路径。

即，如果有两条路径的权重分别为 10->1->10 和 2->2->2，则认为第二条路径比第一条路径更好，因为最小权重 (2) 大于最小权重第一个（1）。

如果任何人都可以找到一种方法来做到这一点，或者只是向我指出一些参考材料的方向，那将非常有用:)

编辑:: 似乎我忘记提及我正在尝试从特定顶点到另一个特定的顶点。 非常重要的一点:/

EDIT2:: 正如下面有人指出的那样，我应该强调边缘权重是非负的。

Answer 1

我正在复制这个答案并添加添加我的算法正确性证明：

我将使用 Dijkstra's 的一些变体。 我直接从维基百科获取了下面的伪代码，只更改了 5 个小东西：

1. 将 dist 重命名为 width （从第 3 行开始）
2. 初始化每个 width到 -infinity（第 3 行）
3. 将源的宽度初始化为 infinity（第 8 行）
4. 将完成标准设置为 -infinity（第 14 行 ） )
5. 修改了更新函数和标志（第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）。 然后，没有比通过 (s, b) 到达 b 更好的方法了，因此您知道 b 的最佳情况容量。 您继续前往已知顶点集的最佳邻居，直到到达所有顶点。

算法正确性证明：

在算法中的任何一点，都会有2组顶点A和B。 A 中的顶点将是已找到正确的最大最小容量路径的顶点。 集合 B 有一些顶点我们还没有找到答案。

归纳假设：在任何一步，集合A中的所有顶点都具有到它们的最大最小容量路径的正确值。 即，所有先前的迭代都是正确的。

基本情况的正确性：当集合A仅具有顶点S时。 那么 S 的值为无穷大，这是正确的。

在当前迭代中，我们设置

val[W] = max(val[W], min(val[V], width_ Between(VW)))

归纳步骤：假设 W 是集合 B 中 val[W 最大的顶点]。 并且 W 从队列中出列，并且 W 已被设置为答案 val[W]。

现在，我们需要证明每个其他 SW 路径的宽度 <= val[W]。 这总是正确的，因为到达 W 的所有其他方式都将经过集合 B 中的某个其他顶点（称为 X）。

对于集合 B 中的所有其他顶点 X，val[X] <= val[W]

因此到 W 的任何其他路径都将受到 val[X] 的约束，该路径永远不会大于 val[W]。

因此 val[W] 的当前估计是最佳的，因此算法计算所有顶点的正确值。

Answer 2

您还可以使用“对答案进行二分搜索”范例。 也就是说，对权重进行二分搜索，测试每个权重 w 是否可以仅使用权重大于 w 的边在图中找到路径。

您可以找到的最大的w（通过二分搜索找到）给出了答案。 请注意，您只需要检查路径是否存在，因此只需 O(|E|) 广度优先/深度优先搜索，而不是最短路径。 所以它总共是 O(|E|*log(max W)) ，与 Dijkstra/Kruskal/Prim 的 O(|E|log |V|) (我也无法立即看到这些证据）。

Answer 3

使用 Prim 的 或 Kruskal 的 算法。 只需修改它们，以便它们在发现您询问的顶点已连接时停止。

编辑：您要求最大最小值，但您的示例看起来像您想要最小最大值。 如果存在最大最小值，克鲁斯卡尔算法将不起作用。

编辑：这个例子是好的，我的错误。 那时只有 Prim 的算法可以工作。

Answer 4

我不确定普里姆会在这里工作。 举个反例：

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的maxmin路径，从1开始会选择1 -->; 2 --> 3 路径，而经过 4 的路径则达到最大-最小距离。

Answer 5

这可以使用 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 并再次处理它的所有邻居。

Answer 6

好吧，在这里回答我自己的问题只是为了尝试获得一些关于我在此处发布之前制定的暂定解决方案的反馈：

每个节点都存储一个“路径片段”，这是迄今为止到其自身的整个路径。

0) 设置当前顶点为起始顶点
1) 生成从此顶点开始的所有路径片段并将它们添加到优先级队列
2) 将片段从优先级队列的顶部取出，并将当前顶点设置为该路径的结束顶点
3) 如果当前顶点是目标顶点，则返回路径
4) goto 1

不过，我不确定这会找到最佳路径，我认为第三步中的退出条件有点雄心勃勃。 不过，我想不出更好的退出条件，因为这个算法不会关闭顶点（一个顶点可以在尽可能多的路径片段中引用），你不能只是等到所有顶点都关闭（就像 Dijkstra 的 for例子）

Answer 7

您仍然可以使用 Dijkstra's！

不要使用 +，而是使用 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)) 相同。

编辑：哦等等，这基本上就是您发布的内容。 哈哈。