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

**אלגוריתם [[ריצ'רד בלמן|בלמן]]-פורד** הוא אלגוריתם הפועל על גרף מכוון וממושקל, ומשמש למציאת המסלול הקל ביותר מצומת אחד מסוים אל כל אחד משאר הצמתים בגרף. בכך, אלגוריתם זה משיג אותה תוצאה כמו אלגוריתם דייקסטרה, אך בניגוד לאלגוריתם דייקסטרה הוא עובד גם כאשר הגרף מכיל קשתות בעלות משקל שלילי. יתר על כן, אם הגרף מכיל מעגל שסכום משקלי קשתותיו שלילי (מה שגורם לכך שאין תשובה מוגדרת לשאלת המסלולים הקצרים) הוא מסוגל לזהות זאת ולהתריע על כך. בגרף בעל \ 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 על הגרף וסידור הקודקודים לפי זמני היציאה שלהם. 

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

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

קטגוריה:אופטימיזציה בדידה
בלמן-פורד