11

私は仕事関連のプロジェクトで友人を助けています。彼はノード a からノード b までの最大容量を計算する必要があり、エッジには容量があります。ただし、a から b へのパスの最大容量は、最小容量のエッジによって制限されます。

簡単なサンプルで説明してみましょう 簡単なサンプル グラフ

したがって、グラフは重み付けされたエッジを持つ有向グラフであり、循環する可能性があります。容量が最大のパスは s->b->t であり、そのエッジが制限を設定しているため、容量は 250 です。

少し読んだところ、このタイプの問題は「最も広いパスの問題」であるか、最大最小容量のパスのようなものであることがわかりましたが、例や方法を説明する疑似コードは見つかりませんでしたこれに取り組むために。

s から t までのすべてのパスを検索し、BFS を使用して、パス内で 1 回のみノードにアクセスできるようにし、パス内の最小値を検索する方法を考えていましたが、それは機能しますか?

4

2 に答える 2

14

Dijkstra の のいくつかのバリアントを使用します。以下の疑似コードをウィキペディアから直接取得し、5 つの小さな点のみを変更しました。

  1. 改名（3dist行width目以降）
  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)。b次に、経由で到達するより良い方法はない(s, b)ため、 の最適なケースの容量がわかりますb。すべての頂点に到達するまで、既知の一連の頂点の最適な隣接点に移動し続けます。

于 2013-08-31T22:02:36.570 に答える