אלגוריתם בלמן-פורד

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

[עריכה] תיאור אינטואיטיבי

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

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

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

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

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

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

[עריכה] תיאור פורמלי

קטע הקוד הבא הוא ויקי-קוד, פסאודו-קוד מוצע לשימוש במאמרים רבים.

// Define datatypes for a graph
record vertex {
    list edges
    real distance
    vertex predecessor
}
record edge {
    node source
    node dest
    real weight
}

function BellmanFord(list vertices, list edges, vertex source)
   // This implementation takes in a graph, represented as lists of vertices
   // and edges, and modifies the vertices so that their distance and
   // predecessor attributes store the shortest paths.

   // Step 1: Initialize graph
   for each vertex v in vertices:
       if v is source then v.distance = 0
       else v.distance = infinity
       v.predecessor = null
   
   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices):       
       for each edge uv in edges:
           u := uv.source
           v := uv.destination             // uv is the edge from u to v
           if v.distance > u.distance + uv.weight
               v.distance := u.distance + uv.weight
               v.predecessor := u

   // Step 3: check for negative-weight cycles
   for each edge uv in u.edges:
       u := uv.source
       v := uv.destination
       if v.distance > u.distance + uv.weight
           error "Graph contains a negative-weight cycle"