שיטת פורד-פלקרסון

שיטה מקובלת למציאת זרימה אופטימלית בגרף היא שיטת פורד-פלקרסון. השיטה היא סכמה כללית, וקיימים מספר אלגוריתמים, בעלי סיבוכיות זמן שונה, המממשים אותה.
הרעיון הבסיסי מאחורי השיטה הוא שיפור איטרטיבי: מתחילים עם פונקציית זרימה שנותנת ערך 0 לכל קשת, ולאחר מכן מחפשים דרכים לשפר אותה על ידי בדיקת מסלולים מהמקור אל הבור. אם מתגלה מסלול אשר ניתן להגדיל את הזרימה בו, הפונקציה מתוקנת בהתאם לכך, והתהליך חוזר על עצמו עד שמתקבלת הפונקציה האופטימלית.
תיאור מדויק של השיטה מתבסס על מושג הרשת השיורית, שמתאר את מצב רשת הזרימה ביחס לפונקציית זרימה נתונה.

אלגוריתם אדמונדס-קארפ

מימוש יעיל אחד של שיטת פורד-פלקרסון מכונה אלגוריתם אדמונדס-קארפ. הרעיון שעומד בבסיסו הוא מציאת מסלול השיפור  על ידי ביצוע אלגוריתם חיפוש לרוחב על הרשת השיורית, כך שהמסלול מ- אל  יהיה מאורך מינימלי (כאשר אורך מסלול הוא מספר הקשתות שבו).
ניתן להוכיח כי סיבוכיות הזמן של אלגוריתם זה היא . סיבוכיות זו נובעת משני גורמים: ראשית, הרצת אלגוריתם חיפוש לרוחב דורשת באופן כללי זמן של , ומתבצעת הרצה אחת של האלגוריתם בכל איטרציה. גם שיפור הזרימה בכל איטרציה דורש זמן של . ניתן להראות כי מספר האיטרציות הוא לכל היותר . כדי לראות זאת משתמשים במושג של קשת קריטית - קשת המופיעה בגרף השיורי באיטרציה i אך לא באיטרציה i+1. עבור אלגוריתם אדמונדס-קארפ מתקיימת התכונה כי אם קשת  שהייתה קריטית באיטרציה מסוימת שבה והופיעה באיטרציה מאוחרת יותר, אז המרחק בין  ו- בגרף השיורי גדל לפחות ב-2 בין האיטרציות, ולכן קשת לא יכולה להיות קריטית יותר מ- פעמים (כי אורך מסלול בגרף הוא ), ומכיוון שמספר הקשתות בגרף השיורי הוא  (לכל קשת בגרף המקורי יש לכל היותר שתי קשתות בגרף השיורי) ובשל העובדה שבכל איטרציה יש לפחות קשת קריטית אחת, נובע כי יש לכל היותר  איטרציות.
האלגוריתם פורסם לראשונה  על ידי יפים דיניץ ב-1970, ופעם נוספת, באופן בלתי תלוי, על ידי ג'ק אדמונדס וריצ'רד קארפ ב-1972, האלגוריתם של דיניץ (אשר יתואר להלן) כלל טכניקות נוספות, אשר קיצרו את זמן הריצה ל-.

אלגוריתם דיניץ

אלגוריתם דיניץ פותח על ידי יפים דיניץ מברית המועצות בשנת 1970, כיום פרופסור במחלקה למדעי המחשב באוניברסיטת בן-גוריון בנגב.
האלגוריתם דומה לאלגוריתם אדמונדס-קארפ, אך הוא מתוחכם ממנו, והדבר בא לידי ביטוי בחסם קטן יותר על זמן הריצה, של . הרעיון הבסיסי באלגוריתם הוא זה של שיטת פורד-פלקרסון - מציאת מסלול שיפור, ושיפור הזרימה לאורכו, אך האלגוריתם של דיניץ מאפשר למצוא מספר מסלולי שיפור "בבת אחת", ובצורה יעילה יותר מאשר באלגוריתם אדמונדס-קארפ. האלגוריתם מבוסס על מושג נוסף לזה של הגרף השיורי - גרף השכבות. בהינתן זרימה וגרף שיורי עבורה, גרף השכבות בנוי על הגרף השיורי, ומחולק ל"שכבות" על פי מרחקי הצמתים שבכל שכבה מהצומת  - בשכבה ה- נמצאים כל הצמתים שמרחקם מ- הוא בדיוק  (כאן מרחק הוא מספר הקשתות שיש לעבור במסלול המחבר את שני הצמתים).
הקשתות היחידות שבגרף השכבות הן אלו שמחברות בין צמתים השייכים לשתי שכבות סמוכות (כלומר, כל קשת שייכת למסלול קצר ביותר מ- אל איזה שהוא צומת).
בהינתן גרף שכבות, ניתן למצוא בקלות יחסית זרימה שתנצל אותו ל"חלוטין".  זרימה שכזו מכונה זרימה חוסמת. מבחינה פורמלית, זרימה חוסמת היא כזו שבכל מסלול מ- אל  בגרף השכבות קיימת קשת  כך ש-.
כדי למצוא זרימה חוסמת בגרף שכבות ניתן להשתמש באלגוריתם חיפוש לעומק, שיחפש מסלולים מ- אל , יעביר זרימה בקשתות על מסלול שנמצא, ויסיר קשתות שהקיבולת שלהן התמלאה. כמו כן אם האלגוריתם מגיע למבוי סתום (צומת שאין ממנו יציאה אך אינו ) הוא מסיר את כל הקשתות שנכנסות אליו. כך מובטח שבכל הרצה של אלגוריתם החיפוש לעומק יקטן מספר הקשתות בגרף השכבות ב-1, ולכן ישנן לכל היותר  הרצות של אלגוריתם החיפוש לעומק, ומכיוון שהאלגוריתם על גרף שכבות שכזה דורש לכל היותר זמן של , מובטח כי מציאת זרימה חוסמת תיקח לכל היותר זמן של .
האלגוריתם של דיניץ מוצא זרימה חוסמת בגרף השכבות ומשפר באמצעותה את הזרימה הקיימת בגרף המקורי. הוא חוזר על התהליך שוב ושוב עד אשר בגרף השכבות אין מסלול המחבר את  אל . ניתן להראות כי בכל איטרציה של האלגוריתם, המרחק בין  ל- בגרף השיורי גדל ממש, ולכן מובטח שהאלגוריתם יסיים תוך  איטרציות, ומכאן הסיבוכיות הכוללת שלו.