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