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

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

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

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

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

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

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

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

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

פסאודו קוד:

Dijakstra algorithm(Graph g,Vertex source)
    create minimum priority queue Q
    foreach vertex in g do
       d[v] = infinty
       prev[v] = NIL     
     d[source] = 0

    while Q is not empty
       u = the vertex in the head of Q
       for each neighbour v of u do
          temp = d[u] + length(u,v)
          if temp < d[v] do
            d[v] = temp
            prev[v] = u

     return d,prev

האלגוריתם מסתיים כאשר קודקוד X החדש הוא היעד או (למציאת כל המסלולים המהירים ביותר) כאשר ביקרנו בכל הקודקודים.
סיבוכיות האלגוריתם תלויה במבנה הנתונים השומר את הקודקודים שטרם ביקרנו בהם, אם מדובר ברשימה או במערך, הסיבוכיות היא ב-$\ O(|V|^{2})$, אם משתמשים בערימה בינארית סיבוכיות הריצה נהיית $\ O(|E|log|V|+|V|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, שעוברת כולה בקודקודים שכבר נקבע מרחקם, היא הקצרה ביותר.

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

ראו גם

• בעיית המסלול הארוך ביותר
• מצגת הסבר - אלגוריתם דייקסטרה

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

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