אלגוריתם פלויד-וורשאל

אלגוריתם פלויד-וורשאל הוא אלגוריתם במדעי המחשב המשמש למציאת המסלולים הקצרים ביותר בין כל שני זוגות צמתים, בגרף ממושקל ומכוון. האלגוריתם מבוסס על פרדיגמת התכנון הדינמי. האלגוריתם פועל גם על גרפים שמכילים קשתות עם משקלים שליליים, בניגוד לאלגוריתם דייקסטרה, אבל לא על גרפים עם מעגל שלילי. סיבוכיות זמן הריצה של האלגוריתם היא $\ \Theta (V^{3})$.

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

תיאור האלגוריתם

האלגוריתם מתבסס על האבחנה הבאה: אם ממספרים את קבוצת הצמתים של הגרף כך שהיא מסומנת $\ \left\{1,2,3,\dots ,n\right\}$ ומסמנים בתור $\ d_{k}(x,y)$ את משקל המסלול הקצר ביותר מהצומת $\ x$ אל הצומת $\ y$ שעובר בצומתי ביניים השייכים אך ורק לקבוצה $\ \left\{1,2,3,\dots ,k\right\}$, אז מתקיים: $\ d_{k}(x,y)=\min \left\{d_{k-1}(x,y),d_{k-1}(x,k)+d_{k-1}(k,y)\right\}$.

כלומר, תמיד מתקיים אחד משניים: אם המסלול הקצר ביותר מ-$\ x$ אל $\ y$ שעובר בצמתים שמספרם לכל היותר $\ k$ לא עובר בצומת שמספרו $\ k$, ברור כי $\ d_{k}(x,y)=d_{k-1}(x,y)$. לעומת זאת, אם המסלול הקצר כן עובר בצומת שמספרו $\ k$ ברור שהוא עובר בו רק פעם אחת (כי אין מעגלים שליליים בגרף, ולכן אם חוזרים לאותו צומת פעמיים מאריכים את המסלול שלא לצורך והוא לא יהיה מינימלי) ואז אפשר לפרק את המסלול לשני מסלולים: אחד שהולך מ-$\ x$ אל $\ k$, ושני שהולך מ-$\ k$ אל $\ y$. שני המסלולים הללו לא עוברים בצמתי ביניים שמספרם גדול מ-$\ k-1$, ולכן סכום משקלם נתון על ידי $\ ,d_{k-1}(x,k)+d_{k-1}(k,y)$. לכן כל מה שנותר הוא לבדוק איזו משתי השיטות עדיפה לכל צומת.

כעת, פעולת האלגוריתם היא זו: הוא מבצע $\ |V|$ איטרציות, כאשר באיטרציה ה-$\ k$ הוא מחשב את $\ d_{k}(x,y)$ לכל זוג צמתים $\ x,y\in V$ ושומר את המידע בטבלה. חישוב $\ d_{k}(x,y)$ מתבצע בזמן $\ O(1)$ בהינתן המידע מהאיטרציה הקודמת, ולכן כל איטרציה של האלגוריתם מתבצעת בזמן $\ O(V^{2})$ (מספרם של זוגות הצמתים האפשריים). לכן זמן הריצה הכולל של האלגוריתם יהיה $\ O(V^{3})$.

המחשת האלגוריתם

1. $\ D_{0}=\ W$
2. עבור $\ k$ מ-1 עד $\ n$ בצע:
   

2.1. עבור $\ x$ מ-1 עד $\ n$ בצע:

2.1.1. עבור $\ y$ מ-1 עד $\ n$ בצע:

2.1.1.1.$\ d_{k}(x,y)=\min \left\{d_{k-1}(x,y),d_{k-1}(x,k)+d_{k-1}(k,y)\right\}$

בסוף, $\ D_{n}$ היא מטריצת אורך המסלולים הקצרים ביותר שעוברים דרך הצמתים $\ \left\{1,2,3,\dots ,n\right\}$.

פסאודו קוד:

 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
 for each edge (u,v)
    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
 for each vertex v
    dist[v][v] ← 0
 for k from 1 to |V|
    for i from 1 to |V|
       for j from 1 to |V|
          if dist[i][j] > dist[i][k] + dist[k][j] 
             dist[i][j] ← dist[i][k] + dist[k][j]
         end if
        end-for
    end-for
end-for

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

 for k from 1 to |V|
    for i from 1 to |V|
       for j from 1 to |V|
          ...
        end-for
    end-for
end-for

באחת משתי האפשרויות:

 for _ from 1 to 3
    for i from 1 to |V|
       for j from 1 to |V|
          for k from 1 to |V|
             ...
          end-for
        end-for
    end-for
end-for

 for _ from 1 to 2
    for i from 1 to |V|
       for k from 1 to |V|
          for j from 1 to |V|
             ...
          end-for
        end-for
    end-for
end-for

האלגוריתם ירוץ כשורה

טיפול במעגלים שליליים

מעגל שלילי הוא מעגל שסכום קשתותיו קטן מאפס. בין שני קודקודים $i,j$ שמשתתפים במעגל שלילי לא קיים מסלול קצר ביותר, כי בכל מעבר על המעגל נקבל מסלול שמשקלו קטן יותר, וניתן להמשיך כך עד אין-קץ. על כן, במקרה של מעגל שלילי האלגוריתם לא יפיק פלט משמעותי. עם זאת, במידה וקיים מעגל שלילי, ניתן להיעזר באלגוריתם על מנת לגלות זאת:

• בתחילה, המרחק בין כל קודקוד $i\in V$ לעצמו הוא 0.
• מסלול $[i,k,...,i]$ יכול לשפר, אם ורק אם סכום קשתותיו שלילי, ז"א מדובר במעגל שלילי.
• על כן, אם קיים קודקוד $i$ שמרחקו מעצמו שלילי, משמעות הדבר שקיים לפחות מעגל שלילי אחד בגרף.

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

ראו גם

• האלגוריתם של ג'ונסון

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

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

הערות שוליים

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

34767207אלגוריתם פלויד-וורשאל