אלגוריתם דייקסטרה

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

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

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

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

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

בתמצית ניתן לסכם את פעולת האלגוריתם כך:

עבור כל קודקוד, מסומן האם ביקרו בו או לא ומה מרחקו מקודקוד המקור. בהתחלה כל הקודקודים מסומנים כאילו לא ביקרו בהם, ומרחקם מוגדר כאינסוף. לולאת האלגוריתם:

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

האלגוריתם מסתיים כאשר קודקוד X החדש הוא היעד או (למציאת כל המסלולים המהירים ביותר) כאשר ביקרנו בכל הקודקודים.
סיבוכיות האלגוריתם תלויה במבנה הנתונים השומר את הקודקודים שטרם ביקרנו בהם, אם מדובר ברשימה או במערך, הסיבוכיות היא ב-\ O(|V|^2), אם משתמשים בערימה בינארית סיבוכיות הריצה משתפרת ל \ O(|E|log|V|) ואם משתמשים בערימת פיבונאצ'י הסיבוכיות היא - \ O(|E|+|V|log|V|)

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

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

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

עקרון זה מאפשר לבסס את מציאת המסלול הקצר ביותר על מעין תכנון דינאמי. הפתרון לבעיה מצוי בפתרון לתת הבעיות שלה. המסלול הקצר ביותר מ-S ל-T יימצא על סמך המסלולים הקצרים ביותר מ-S לקודקודים שקדמו ל-T.

עיקרון שני הוא חמדני. בכל שלב מצויים במצב שבו נקבע מרחקם הקצר ביותר מ-S של חלק מהקודקודים, אך לא נקבע מרחקם של קודקודים אחרים. הרעיון החמדני קובע כי בכל שלב יש להתבונן באלו מהקודקודים שלא נקבע מרחקם ושיש אליהם קשת מקודקודים שמרחקם כבר נקבע, וליטול מקבוצה זו את הקודקוד שהדרך אליו מ-S, שעוברת כולה בקודקודים שכבר נקבע מרחקם, היא הקצרה ביותר.

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

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

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

  1. ^ "A note on two problems in connexion with graphs" (1959). Numerische Mathematik 1: 269–271. doi:10.1007/BF01386390. 

קישורים חיצוניים[עריכת קוד מקור | עריכה]