在图中查找具有最大最小容量的路径 [英] Finding path with maximum minimum capacity in graph

问题描述

我正在帮助一个与工作相关的项目的朋友，他需要计算从节点 a 到节点 b 的最大容量，其中边缘具有容量.然而，从 a 到 b 的路径中的最大容量受到容量最低的边的限制.

I am helping a friend with a work related project where, he needs to calculate the maximum capacity from a node a to a node b, where the edge has a capacity. However the maximum capacity in a path from a to b is limited by the edge with the lowest capacity.

让我试着用一个简单的例子来解释

Let me try to explain with a simple sample

所以这个图是一个带加权边的有向图，它可以是循环的.具有最高容量的路径将是 s->b->t 并且容量为 250，因为该边正在设置限制.

So the graph is a directed graph with weighted edges, and it can be cyclic. The path with the highest capacity would be s->b->t and have the capacity of 250, since that edge is setting the limit.

我做了一些阅读，发现这种类型的问题是一个最宽路径问题" 或者我将其称为具有最大最小容量的路径，但我还没有找到任何示例或任何伪代码来解释如何解决这个问题.

I have done a bit of reading and found out that this type of problem is a "Widest path problem" or I would call it something like a path with maximum minimum capacity, but I haven't found any examples or any pseudo code explaining how to tackle this.

我正在考虑寻找从 s 到 t 的所有路径，使用 BFS 并且以某种方式只允许在路径中访问一次节点，然后在路径中找到最小值，这行得通吗?

I was thinking something in the lines of finding all paths from s to t, using BFS and somehow only to allow visiting a node once in a path, and then find the minimum value in the path, would that work?

推荐答案

我会使用 Dijkstra 的一些变体.我直接从维基百科上拿了下面的伪代码，只改动了5个小东西:

I would use some variant of Dijkstra's. I took the pseudo code below directly from Wikipedia and only changed 5 small things:

1. 将 dist 重命名为 width(从第 3 行开始)
2. 将每个width初始化为-infinity(第3行)
3. 将源的宽度初始化为infinity(第8行)
4. 将完成条件设置为 -infinity(第 14 行)
5. 修改了更新函数和符号(第 20 + 21 行)

1. Renamed dist to width (from line 3 on)
2. Initialized each width to -infinity (line 3)
3. Initialized the width of the source to infinity (line 8)
4. Set the finish criterion to -infinity (line 14)
5. Modified the update function and sign (line 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 的最佳情况容量.您继续前往已知顶点集的最佳邻居，直到到达所有顶点.

Some (handwaving) explanation why this works: you start with the source. From there, you have infinite capacity to itself. Now you check all neighbors of the source. Assume the edges don't all have the same capacity (in your example, say (s, a) = 300). Then, there is no better way to reach b then via (s, b), so you know the best case capacity of b. You continue going to the best neighbors of the known set of vertices, until you reach all vertices.

这篇关于在图中查找具有最大最小容量的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！