Fortfahren Sie den Ford-Fulkelson

Question

Ich versuche, die Ford-Fulkerson-Methode zu lernen. Ich habe ein Beispiel für das Üben zusammengestellt und irgendwann kann ich den Fluss nicht weiter erhöhen, aber ich weiß, dass der Fluss höher sein könnte.

Zunächst einmal habe ich den Weg s -> 1 -> 2 -> t erhöht. Und jetzt kann ich keinen Weg finden, den Fluss zu erhöhen. Ich weiß, dass, wenn ich den Pfad a -> 1 -> 5 -> 6 -> t zuerst nahm, dann könnte ich Pfad s -> 3 -> 4 -> 2 -> t inkrementieren, aber wenn ich es implementieren musste, würde ich nicht wissen, wie es geht.

Was mache ich falsch?

Answer 1

Ich habe es herausgefunden. Ich wusste nicht, dass es möglich ist, Kanten in die entgegengesetzte Richtung zum Pfeil zu verwenden.

So können wir den Weg s -> 3 -> 4 -> 2 -> 1 -> 5 -> 6 -> t überqueren.

Dann erhalten wir das erwartete Ergebnis.