6

我正在尝试制定一种算法来找到穿过有向图的路径。这不是一条传统的道路，我找不到任何关于已经完成的类似事情的参考。

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

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

如果有人能想出办法做到这一点，或者只是向我指出一些参考材料的方向，那将非常有用:)

编辑:: 似乎我忘了提到我正试图从一个特定的顶点到另一个特定的顶点。那里很重要：/

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

4

7 回答 7

8

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

我会使用Dijkstra 的一些变体。我直接从维基百科获取了下面的伪代码，只改变了 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）。那么，没有比bvia更好的到达方式了(s, 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] 的估计是最优的，因此算法计算所有顶点的正确值。

于 2014-04-06T05:15:25.143 回答
4

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

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

于 2009-05-16T19:57:41.203 回答
3

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

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

编辑：这个例子没问题，我的错。只有 Prim 的算法会起作用。

于 2009-05-16T19:50:53.293 回答
2

我不确定 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 的路径获得最大最小距离。

于 2013-08-23T18:29:50.977 回答
1

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

于 2009-05-16T20:12:47.673 回答
0

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

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

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

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

于 2009-05-16T20:50:13.887 回答
-1

你仍然可以使用 Dijkstra 的！

不要使用 +，而是使用 min() 运算符。
此外，您需要确定 heap/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))。

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

于 2009-05-16T21:48:43.400 回答