找到路径与图中最大最小容量 [英] Finding path with maximum minimum capacity in graph

问题描述

我帮助与工作有关的项目，其中，他需要计算从节点的最大容量到节点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.

我已经做了一些阅读和发现，这类问题是最宽的路径问题 或我称之为像最大容量最小的路径，但我还没有找到任何例子或者伪code解释如何解决这个问题。

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的。我从维基百科把伪code以下直接和唯一的改变了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 到宽度（从第3行）
2. 初始化，并且每个宽度到 -infinity （3号线）
3. 初始化源的宽度无限（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

部分（handwaving）的解释，为什么这个工程：启动与源。从那里，你有无限的能力本身。现在你检查源的所有邻居。假设边缘并不都具有相同的能力（在你的榜样，说（S，A）= 300 ）。那么，有没有更好的方式来达到 B 通过则（S，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屋！