Ford-Fulkerson アルゴリズムの私の分析は正しく出ていません。たとえば、次のグラフを見てください。
_____>4___>_
| |
0--->1---->3------6
| | |
2--->5--------->---
ノード 0 はソース、ノード 6 はターミナル ノードであり、すべてのエッジの制限は 1 です。ただし、ノード 0 から 1 へのエッジの制限は 2 です。フローが 0->1->3->6 および 0- >1->4->6 および 0->2->5->6 の場合、グラフのフローは 3 です。ただし、フローが 0->1 から開始する場合は、0->1->3 を選択します。 ->6 と 0->1->5->6 では、5->6 は既に占有されているため、0->2->5->6 からはもう移動できません。0->1 の制限は 2 であるため、0->1 から開始できるのは 2 回だけです。したがって、グラフのフローは 2 です。明らかに、グラフの可能な最大フローは 2 ではなく 3 である必要があります。アルゴリズムはこの問題を処理し、常に答えとして 3 を返しますか?