• Artikel
• Bearbeiten
• Historie
• Druckansicht

Ford-Fulkerson

Der Ford Fulkerson Algorithmus berechnet durch sukzessive Verbesserung (Hinzunahme nutzbarer Pfade) den maximalen Fluss durch einen Graphen

Beispiel

Betrachten Sie das Beispiel rechts Suche den Weg von "A nach E"

• Pfad AB BD DE Kapazität 2
• Pfad AC CD DE Kapazität 3
• Pfad AC CE Kapazität 4
• Keine weiteren nutzbaren Pfade

Ergebnis: Der maximale Fluss wird durch [AC,CE] erreicht

Algorithmus

• Merke für jede Kante (k,l) die aktuelle genutzte Kapazität und die verfügbare Kapazität
• Solange es noch einen nutzbaren Pfad gibt
  • Verwende den nutzbaren Pfad
  • Aktualisiere die genutzte Kapazität
• Wenn kein nutzbarer Pfad mehr vorhanden, handelt es sich um den maximalen Fluss

Weblinks

• Dijkstra Java Applet