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

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

סיבוכיות זמן	O(|n|^3)
סיבוכיות מקום	O(|V|^2)
ממציא	ברנארד רוי
נקרא על שם	רוברט פלויד, סטיבן וורשאל
הומצא	1959

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

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

תהי W מטריצת משקלי הקשתות: כלומר w(i,j) הוא משקל הקשת המחברת את i עם j. (משקל זה הוא אין-סוף אם אין קשת בינהם).

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$ שמרחקו מעצמו שלילי, משמעות הדבר שקיים לפחות מעגל שלילי אחד בגרף.

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

ראו גם

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

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

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

• אלגוריתם פלויד-וורשאל, באתר MathWorld (באנגלית)