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

שיטה מקובלת למציאת זרימה אופטימלית בגרף היא שיטת פורד-פלקרסון^[1]. השיטה היא סכמה כללית, וקיימים מספר אלגוריתמים, בעלי סיבוכיות זמן שונה, המממשים אותה.

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

תיאור מדויק של השיטה מתבסס על מושג הרשת השיורית, שמתאר את מצב רשת הזרימה ביחס לפונקציית זרימה נתונה.

רשת שיורית

בהינתן זרימה, ניתן לבדוק כיצד ניתן לשפר אותה (כלומר, להגדיל את ערך הזרימה) באמצעות שימוש בגרף המכונה "הרשת השיורית", אשר מייצג את הקשתות שדרכן ניתן להגדיל את הזרימה.

רשת זרימה עם זרימה כל שהיא (לא מקסימלית)

מבחינה פורמלית, לכל זוג צמתים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (u,v)} מגדירים את הקיבול השיורי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (u,v)} על ידי:

$\ c_{f}(u,v)=c(u,v)-f(u,v)$

הקיבול השיורי יכול להיות גדול מהקיבול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c(u,v)} שכן ערך פונקציית הזרימה יכול להיות שלילי. כדי להבין זאת יש לזכור כי הקיבול השיורי מייצג את כמות הזרימה נטו שניתן להעביר מהצומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u} אל הצומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} - ואת הזרימה נטו ניתן להגדיל גם על ידי הקטנת הזרימה בכיוון ההפוך. בשל כך, הקיבול השיורי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (u,v)} יכול להיות חיובי אף אם אין כלל קשת מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u} אל $\ v$ אלא רק בכיוון ההפוך (ואז קיבול שיורי חיובי פירושו שכרגע יש זרימה בכיוון ההפוך ואותה ניתן להקטין).

הרשת השיורית היא גרף מכוון שצמתיו הם צומתי רשת הזרימה המקורית, ויש בו קשת בין כל זוג צמתים שעבורו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c_f(u,v)>0} . כלומר, הגרף מייצג את כל המקומות שבהם ניתן להעביר זרימה נוספת ברשת המקורית.

קובץ:Network flow residual.png

הרשת השיורית עבור רשת הזרימה והזרימה שהוצגו קודם

מסלול שיפור הוא מסלול מהמקור אל הבור ברשת השיורית. קיום של מסלול שיפור שכזה פירושו שברשת המקורית ניתן להעביר זרימה נוספת דרך אותו מסלול.

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

השיטה מסיימת את פעולתה לאחר שלא נמצאו מסלולי שיפור עבור הזרימה הנוכחית. במקרה זה, הזרימה היא אופטימלית. המשפט המראה זאת מכונה משפט זרימה־מקסימלית חתך־מינימלי.

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

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

לכל קשת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (u,v)\in E} בצע:
1. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(u,v)=0}
2. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(v,u)=0}
כל עוד קיים מסלול מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} ברשת השיורית המושרית על ידי $\ f$ $\ f$ , בצע, עבור מסלול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} מסוים:
1. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c_f(p)=\min\left\{c_f(u,v)|(u,v)\isin p\right\}}
2. לכל קשת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (u,v)\isin p} בצע:
  1. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(u,v)=f(u,v)+c_f(p)}
  2. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(v,u)=-f(u,v)}

רשת זרימה בה אלגוריתם פורד-פלקרסון עלול לדרוש זמן ריצה מסדר גודל של ערך הזרימה המקסימלית

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

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

עם זאת, גם כאשר מובטח כי האלגוריתם יסיים את ריצתו, סיבוכיות הזמן תלויה בערכה המקסימלי של פונקציית הזרימה: ניתן להראות כי הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(|E|f^*)} , כאשר $\ f^{*}$ הוא ערך הזרימה המקסימלי.

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

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

מימוש יעיל אחד של שיטת פורד-פלקרסון מכונה אלגוריתם אדמונדס-קארפ. הרעיון שעומד בבסיסו הוא מציאת מסלול השיפור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} על ידי ביצוע אלגוריתם חיפוש לרוחב על הרשת השיורית, כך שהמסלול מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} יהיה מאורך מינימלי (כאשר אורך מסלול הוא מספר הקשתות שבו).

ניתן להוכיח כי סיבוכיות הזמן של אלגוריתם זה היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(|V|*|E|^2)} . סיבוכיות זו נובעת משני גורמים: ראשית, הרצת אלגוריתם חיפוש לרוחב דורשת באופן כללי זמן של $\ O(E)$ , ומתבצעת הרצה אחת של האלגוריתם בכל איטרציה. גם שיפור הזרימה בכל איטרציה דורש זמן של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(|E|)} . ניתן להראות כי מספר האיטרציות הוא לכל היותר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(VE)} . כדי לראות זאת משתמשים במושג של קשת קריטית - קשת המופיעה בגרף השיורי באיטרציה i אך לא באיטרציה i+1. עבור אלגוריתם אדמונדס-קארפ מתקיימת התכונה כי אם קשת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (u,v)} שהייתה קריטית באיטרציה מסוימת שבה והופיעה באיטרציה מאוחרת יותר, אז המרחק בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} בגרף השיורי גדל לפחות ב-2 בין האיטרציות, ולכן קשת לא יכולה להיות קריטית יותר מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(V)} פעמים (כי אורך מסלול בגרף הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(V)} ), ומכיוון שמספר הקשתות בגרף השיורי הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(E)} (לכל קשת בגרף המקורי יש לכל היותר שתי קשתות בגרף השיורי) ובשל העובדה שבכל איטרציה יש לפחות קשת קריטית אחת, נובע כי יש לכל היותר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(VE)} איטרציות.

האלגוריתם פורסם לראשונה על ידי יפים דיניץ ב-1970^[2], ופעם נוספת, באופן בלתי תלוי, על ידי ג'ק אדמונדס וריצ'רד קארפ ב-1972^[3], האלגוריתם של דיניץ (אשר יתואר להלן) כלל טכניקות נוספות, אשר קיצרו את זמן הריצה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(V^2E)} .

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

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

האלגוריתם דומה לאלגוריתם אדמונדס-קארפ, אך הוא מתוחכם ממנו, והדבר בא לידי ביטוי בחסם קטן יותר על זמן הריצה, של $\ O(V^{2}E)$ . הרעיון הבסיסי באלגוריתם הוא זה של שיטת פורד-פלקרסון - מציאת מסלול שיפור, ושיפור הזרימה לאורכו, אך האלגוריתם של דיניץ מאפשר למצוא מספר מסלולי שיפור "בבת אחת", ובצורה יעילה יותר מאשר באלגוריתם אדמונדס-קארפ. האלגוריתם מבוסס על מושג נוסף לזה של הגרף השיורי - גרף השכבות. בהינתן זרימה וגרף שיורי עבורה, גרף השכבות בנוי על הגרף השיורי, ומחולק ל"שכבות" על פי מרחקי הצמתים שבכל שכבה מהצומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} - בשכבה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} נמצאים כל הצמתים שמרחקם מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} הוא בדיוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} (כאן מרחק הוא מספר הקשתות שיש לעבור במסלול המחבר את שני הצמתים).

הקשתות היחידות שבגרף השכבות הן אלו שמחברות בין צמתים השייכים לשתי שכבות סמוכות (כלומר, כל קשת שייכת למסלול קצר ביותר מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} אל איזה שהוא צומת).

בהינתן גרף שכבות, ניתן למצוא בקלות יחסית זרימה שתנצל אותו ל"חלוטין". זרימה שכזו מכונה זרימה חוסמת. מבחינה פורמלית, זרימה חוסמת היא כזו שבכל מסלול מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} בגרף השכבות קיימת קשת $\ (u,v)$ כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c(u,v)=f(u,v)} .

כדי למצוא זרימה חוסמת בגרף שכבות ניתן להשתמש באלגוריתם חיפוש לעומק, שיחפש מסלולים מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} , יעביר זרימה בקשתות על מסלול שנמצא, ויסיר קשתות שהקיבולת שלהן התמלאה. כמו כן אם האלגוריתם מגיע למבוי סתום (צומת שאין ממנו יציאה אך אינו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} ) הוא מסיר את כל הקשתות שנכנסות אליו. כך מובטח שבכל הרצה של אלגוריתם החיפוש לעומק יקטן מספר הקשתות בגרף השכבות ב-1, ולכן ישנן לכל היותר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(E)} הרצות של אלגוריתם החיפוש לעומק, ומכיוון שהאלגוריתם על גרף שכבות שכזה דורש לכל היותר זמן של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(V)} , מובטח כי מציאת זרימה חוסמת תיקח לכל היותר זמן של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(VE)} .

האלגוריתם של דיניץ מוצא זרימה חוסמת בגרף השכבות ומשפר באמצעותה את הזרימה הקיימת בגרף המקורי. הוא חוזר על התהליך שוב ושוב עד אשר בגרף השכבות אין מסלול המחבר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} . ניתן להראות כי בכל איטרציה של האלגוריתם, המרחק בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} בגרף השיורי גדל ממש, ולכן מובטח שהאלגוריתם יסיים תוך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(V)} איטרציות, ומכאן הסיבוכיות הכוללת שלו.

הערות שוליים

^ Ford, L. R.; Fulkerson, D. R. (1956). "Maximal flow through a network". Canadian Journal of Mathematics. 8: 399–404.
^ Dinic, E. A. (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation". Soviet Math. Doklady. Doklady. 11: 1277–1280.
^ Edmonds, Jack; Karp, Richard M. (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM. Association for Computing Machinery. 19 (2): 248–264. doi:10.1145/321694.321699.

[1] Ford, L. R.; Fulkerson, D. R. (1956). "Maximal flow through a network". Canadian Journal of Mathematics. 8: 399–404.

[2] Dinic, E. A. (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation". Soviet Math. Doklady. Doklady. 11: 1277–1280.

[3] Edmonds, Jack; Karp, Richard M. (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM. Association for Computing Machinery. 19 (2): 248–264. doi:10.1145/321694.321699.

[1]

[2]

[3]