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

Question

我正在尝试找出一种算法,用于在有向图上找到路径.这不是一个传统的路径,我找不到任何像这样的东西的引用.

我想找到具有最大最小重量的路径.

即如果有两条路径的权重为10-> 1-> 10且2-> 2-> 2则第二路径被认为优于第一路径,因为最小权重(2)大于第一路径的最小权重( 1).

如果有人可以找到一种方法来做到这一点,或者只是指向一些参考资料的方向,那将是非常有用的:)

编辑::我似乎忘了提到我正试图从一个特定的顶点到另一个特定的顶点.非常重要的一点:/

EDIT2 ::如下所述,我应该强调边缘权重是非负的.

Answer 1

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

我会使用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

一些(handwaving)解释为什么这样做:你从源头开始.从那里,你拥有无限的能力.现在检查源的所有邻居.假设边缘并不都具有相同的容量(例如,在您的示例中(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(VW)))

归纳步骤:假设,W是集合B中具有最大val [W]的顶点.并且W从队列中出队,W已经设置了答案值[W].

现在,我们需要显示每个其他SW路径的宽度<= val [W].这将永远是正确的,因为到达W的所有其他方式将通过集合B中的某些其他顶点(称为X).

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

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

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

Answer 2

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

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

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