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

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

סיבוכיות זמן	\Theta (|V| |E|)
סיבוכיות מקום	\Theta (|V|)
ממציא	ריצ'רד בלמן (1958), L. R. Ford, Jr. (1956), Edward F. Moore (1957)
נקרא על שם	ריצ'רד בלמן, L. R. Ford, Jr.

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

תיאור אינטואיטיבי

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

לכל צומת $\ v$ בגרף אנו מתאימים משתנה $\ d[v]$ שמייצג את משקל המסלול הקל ביותר שנמצא עד כה של מסלול מ-$\ s$ (הצומת ההתחלתי) ועד $\ v$. בתחילת ריצת האלגוריתם $\ d[v]=\infty$ לכל צומת שאינו $\ s$ (כי עדיין לא נמצא מסלול כלשהו), ואילו $\ d[s]=0$ (כי המסלול הטריוויאלי מ-$\ s$ אל עצמו שאינו מכיל קשתות הוא במשקל 0).

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

כאשר מבצעים פעולת הקלה על קשת $\ (u,v)$, בודקים האם מתקיים $\ d[v]>d[u]+w(u,v)$ כאשר $\ w(u,v)$ הוא משקל הקשת. אם אי השוויון מתקיים, פירוש הדבר שהמסלול הקל ביותר אל $\ v$ שהיה ידוע עד כה הוא כבד יותר מאשר המסלול שמגיע אל $\ u$ במסלול הקצר ביותר שידוע עבורו, ואז עובר מ-$\ u$ אל $\ v$ באמצעות הקשת $\ (u,v)$. לכן, אם אי השוויון מתקיים, מעדכנים את $\ u$ להיות הקודם ל-$\ v$ במסלול הקל ביותר, ומעדכנים את $\ d[v]$ להיות שווה ל-$\ d[u]+w(u,v)$.

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

לאחר סיום ריצת האיטרציות, האלגוריתם עובר פעם נוספת על כל הקשתות ובודק האם עדיין מתקיים $\ d[v]>d[u]+w(u,v)$, כלומר "עדיין יש מה לתקן". זה יכול לקרות אם ורק אם הגרף מכיל מעגלים שליליים, ולכן אפשר לתקן אותו "עד אינסוף", כי כל מסלול יכול להיכנס אל תוך המעגל השלילי וללכת עליו כמה פעמים שירצה כדי להקטין את משקלו.

תיאור פורמלי

קטע הקוד הבא הוא פסאודו קוד.

// Define datatypes for a graph
record vertex {
    list edges
    real distance
    vertex predecessor
}
record edge {
    node source
    node destination
    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) - 1:       
       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"

אפשרויות שיפור

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

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

קישורים חיצוניים

מדיה וקבצים בנושא אלגוריתם בלמן-פורד בוויקישיתוף