אלגוריתם פלויד-וורשאל
מתוך ויקיפדיה, האנציקלופדיה החופשית
אלגוריתם פלויד-וורשאל הוא אלגוריתם במדעי המחשב המשמש למציאת המסלולים הקצרים ביותר בין כל שני זוגות צמתים, בגרף ממושקל ומכוון. האלגוריתם מבוסס על פרדיגמת התכנון הדינמי. האלגוריתם פועל גם על גרפים שמכילים קשתות עם משקלות שליליים, אבל לא על גרפים עם מעגל שלילי. סיבוכיות זמן הריצה של האלגוריתם היא
.
[עריכה] תיאור האלגוריתם
האלגוריתם מתבסס על האבחנה הבאה: אם ממספרים את קבוצת הצמתים של הגרף כך שהיא מסומנת
ומסמנים בתור
את משקל המסלול הקצר ביותר מהצומת
אל הצומת
שעובר בצמתי ביניים השייכים אך ורק לקבוצה
, אז מתקיים:
.
כלומר, תמיד מתקיים אחד משניים: אם המסלול הקצר ביותר מ-
אל
שעובר בצמתים שמספרם לכל היותר
לא עובר בצומת שמספרו
, ברור כי
. לעומת זאת, אם המסלול הקצר כן עובר בצומת שמספרו
ברור שהוא עובר בו רק פעם אחת (כי אין מעגלים שליליים בגרף, ולכן אם חוזרים לאותו צומת פעמיים מאריכים את המסלול שלא לצורך והוא לא יהיה מינימלי) ואז אפשר לפרק את המסלול לשני מסלולים: אחד שהולך מ-
אל
, ושני שהולך מ-
אל
. שני המסלולים הללו לא עוברים בצמתי ביניים שמספרם גדול מ-
, ולכן סכום משקלם נתון על ידי
. לכן כל מה שנותר הוא לבדוק איזו משתי השיטות עדיפה לכל צומת.
כעת, פעולת האלגוריתם היא זו: הוא מבצע
איטרציות, כאשר באיטרציה ה-
הוא מחשב את
לכל זוג צמתים
ושומר את המידע בטבלה. חישוב
מתבצע בזמן
בהינתן המידע מהאיטרציה הקודמת, ולכן כל איטרציה של האלגוריתם מתבצעת בזמן
(מספרם של זוגות הצמתים האפשריים). לכן בסה"כ זמן ריצת האלגוריתם יהיה
.

