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

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

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

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

לכל צומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} בגרף אנו מתאימים משתנה $\ d[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 \ v} . בתחילת ריצת האלגוריתם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ d[v]=\infty} לכל צומת שאינו הפענוח נכשל (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 \ d[s]=0} (כי המסלול הטריוויאלי מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} אל עצמו שאינו מכיל קשתות הוא במשקל 0).

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

כאשר מבצעים פעולת הקלה על קשת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (u,v)} , בודקים האם מתקיים $\ d[v]>d[u]+w(u,v)$ כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ w(u,v)} הוא משקל הקשת. אם אי השוויון מתקיים, פירוש הדבר שהמסלול הקל ביותר אל הפענוח נכשל (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} במסלול הקצר ביותר שידוע עבורו, ואז עובר מ-הפענוח נכשל (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} להיות הקודם ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} במסלול הקל ביותר, ומעדכנים את $\ d[v]$ להיות שווה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ d[u]+w(u,v)} .

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

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

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

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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