ראשי > זרימה > שיטת פורד-פולקרסון המשך

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

אז מהי שיטת פורד - פולקרסון ?

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

פסאודו קוד

1. for each edge e in E do
2.      f(e) = 0
3. build new residual graph
4. while there is a simple path P from s to t in the residual graph
5.      do flow the maximum c in P
6.      for each edge (u,v) in P do
7.            f(u,v) = f(u,v) + c
8.      build new residual graph

הסבר :

האלגוריתם מתחיל במתן זרימה אפס לכל קשת בגרף, ובנית הגרף השיורי (שורות 1-2), שים לב כי בשלב הראשון הגרף השיורי זהה לחלוטין לגרף.

כל עוד יש מסלול פשוט בין s ל t בגרף השיורי (שורה 4), נמצא אותו ונזרים את הזרימה המקסימלית שאפשר (זרימה זו נקבעת לפי הקיבול המינימלי על המסלול).

עבור כל קשת במסלול שמצאנו, נוסיף את הזרימה החדשה לזרימה שכבר קיימת בגרף המקורי (שורות 6-7).
נבנה גרף שיורי חדש ונחזור על התהליך שוב. (משורה 4).

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

דוגמת הרצה