פורד־פלקרסון

מחשב את הזרימה המקסימלית ברשת זרימה.

שלב 1 מתוך 8

מצא זרימה מקסימלית מ־"s" ל־"t" באמצעות אדמונדס־קארפ (BFS). כל הזרימות מתחילות ב־0.

זרימה מקסימלית

מסלול מגדיל

—

צוואר בקבוק

—

▶אלגוריתם

flow = 0; initialise residual graph
while augmenting path P exists:
P ← find path from s to t
bottleneck = min residual cap on P
augment flow along P by bottleneck
flow += bottleneck
return flow  // no more augmenting paths

מקרא

מקור / בור

על המסלול

קשת רוויה

קשתות קדמיות: זרימה/קיבולת.
קשתות ירוקות: שארית לאחור (קיבולת זרימה חוזרת).

הרשת המקורית

רשת השארית

1 / 8מהירות