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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

תיאור האלגוריתם[עריכת קוד מקור | עריכה]

האלגוריתם מתבסס על האבחנה הבאה: אם ממספרים את קבוצת הצמתים של הגרף כך שהיא מסומנת \ \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\isin 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_k היא מטריצת אורך המסלולים הקצרים ביותר שעוברים דרך הצמתים \ \left\{1,2,3,\dots,k\right\}.

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Eric W. Weisstein. Floyd-Warshall Algorithm. Wolfram MathWorld. אוחזר ב־13 November 2009.