O（E）時間内のネットワークフローグラフの残差グラフでソースからターゲットへのパスを見つける

Question

フローネットワークGとそれらの（エッジ）容量が与えられ、各エッジに容量と（エッジ）が流れ、フローF：Fが最大フローかどうかを調べるために、残差グラフにソースからターゲットまでのパスが存在するかどうかをチェックしたい。

O（E）時間に行うことはできますか？

誰かに私と一緒に行くための助けを与えることができ、私はそれを行う必要があることを示すかもしれませんか？

• は

Answer 1

Iが流れるネットワークG及びそれらの（エッジ）の容量と（エッジ）が与えられ、各エッジ流れる午前編集されています。ソースからターゲットまでのパスが存在するかどうかを確認したい。あなたはだけソースからターゲットにパスが存在するかどうかを確認したい場合は

は、その後、残留グラフを必要としません。

残差グラフがあれば、このようなパスがあるかどうかを確認するために、BFS Algoritmを調整するだけです。私はこれがO（| E |）でできることを発見しました。

BFSアルゴリズムの時間複雑度は、であり、O(E)ではありません。

しかし、私は残余のグラフを持たないので、最初に計算してから進めなければならない場合は、全体的な時間の複雑さを増やすかどうかO（| E |）？

残余のグラフの計算には、O(V+E)より多くの時間が必要です。

maximum flow problemを解決しようとすると、時間複雑度がO(E max|f|)のford-fulkerson algorithmのような標準アルゴリズムを使用してみませんか？

---

更新 I Fが最大流量であるかどうかを調べるために、残留グラフにソースからターゲットにパスが存在するかどうかを確認したい

。 O（E）時間にそれを行うことは可能ですか？

有向グラフ内の2つのノード間にパスがあるかどうかをチェックするには、O(V+E)時間が必要です。以前に述べたように、BFSまたはDFSのいずれかを使用することができます。