קרא בשפות אחרות: English, 한국어, 日本語, 简体中文, 繁體中文, Українська, Español, Français, Deutsch, עברית
אלגוריתם דייקסטרה הוא אלגוריתם למציאת המסלולים הקצרים ביותר בין צמתים בגרף, שיכול לייצג למשל רשת כבישים.
לאלגוריתם יש מספר גרסאות; הגרסה המקורית של דייקסטרה מצאה את המסלול הקצר ביותר בין שני צמתים, אך גרסה נפוצה יותר קובעת צומת אחד כ"צומת מקור" ומוצאת את המסלולים הקצרים ביותר ממנו לכל שאר הצמתים בגרף, וכך נוצרת עץ מסלולים קצרים (Shortest-Path Tree).
אלגוריתם דייקסטרה למציאת המסלול הקצר ביותר בין a ל־b.
הוא בוחר את הצומת שלא ביקרו בו שעד כה יש לו את המרחק הקטן ביותר,
מחשב את המרחק דרכו לכל שכן שלא ביקרו בו,
ומעדכן את המרחק אם נמצא מסלול קצר יותר.
כאשר מסיימים לבדוק את כל השכנים, מסמנים את הצומת כ"ביקור הושלם" (אדום).
- מערכות GPS / ניווט
- אופטימיזציה של מסלולי תחבורה ציבורית וטיסות
- ניתוב באינטרנט (פרוטוקולים OSPF, IS-IS)
- אופטימיזציה של תעבורת רשת וזמני השהיה
- חיפוש מסלולים במשחקים (המסלול הקצר ביותר במפה)
- אופטימיזציה של מסלולי משלוחים ולוגיסטיקה
- תכנון רשתות תחבורה ושרשראות אספקה
נניח שיש לנו גרף משוקלל של צמתים, שבו לכל קשת יש ערך מרחק בין צמתים.
לדוגמה, המרחק בין הצומת A לצומת B הוא 7 מטרים (או בקיצור 7m).
האלגוריתם משתמש בתור עדיפויות כדי תמיד לבחור את הצומת שלא ביקרו בו עם המרחק הקטן ביותר מהצומת ההתחלתי.
צומת ההתחלה, על פי ההגדרה, נמצא במרחק 0m מעצמו.
לכן מתחילים ממנו — הצומת היחיד בתור העדיפויות בתחילת התהליך.
שאר הצמתים יתווספו לתור במהלך המעבר בגרף (בעת ביקור בשכנים).
כל שכן של הצומת שנשלף מהתור נבדק כדי לחשב את המרחק אליו מהמקור.
לדוגמה, המרחק מ־A ל־B הוא 0m + 7m = 7m.
בכל פעם שמבקרים שכן חדש שטרם נבדק, מוסיפים אותו לתור העדיפויות, כאשר העדיפות נקבעת לפי המרחק מהמקור.
הצומת B נוסף לתור העדיפויות המינימלי כדי לעבור עליו מאוחר יותר.
מבקרים את השכן הבא של A, שהוא C.
המרחק מ־A ל־C הוא 0m + 9m = 9m.
הצומת C נוסף גם הוא לתור העדיפויות.
כנ"ל לגבי הצומת F.
המרחק הנוכחי מ־A ל־F הוא 0m + 14m = 14m.
F נוסף לתור כדי לעבור עליו בהמשך.
לאחר שכל השכנים של הצומת הנוכחי נבדקו, מוסיפים אותו לקבוצת visited.
אין צורך לבקר בו שוב.
כעת נשלוף מהתור את הצומת הקרוב ביותר למקור (בעל המרחק הקצר ביותר) ונתחיל לבקר את שכניו.
אם הצומת שבו אנו מבקרים (למשל C) כבר נמצא בתור,
המשמעות היא שכבר חישבנו את המרחק אליו, אבל ממסלול אחר (A → C).
אם המרחק הנוכחי (דרך המסלול A → B → C) קצר יותר, נעדכן אותו;
אם ארוך יותר — נשאיר אותו כפי שהוא.
לדוגמה, בעת ביקור ב־C דרך B (A → B → C), המרחק הוא 7m + 10m = 17m.
זה ארוך יותר מהמרחק שכבר נרשם (9m), ולכן אין עדכון.
מבקרים שכן נוסף של B, שהוא D.
המרחק ל־D הוא 7m + 15m = 22m.
מכיוון שטרם ביקרנו ב־D והוא אינו בתור, נוסיף אותו עם עדיפות (מרחק) של 22m.
בשלב זה כל שכניו של B נבדקו, ולכן נוסיף את B לקבוצת visited.
לאחר מכן נשלוף את הצומת הקרוב ביותר למקור מהתור.
מבקרים את השכנים הלא-מבוקרים של C.
המרחק ל־F דרך C (המסלול A → C → F) הוא 9m + 2m = 11m.
זה קצר יותר מהמרחק שנרשם קודם (14m ל־A → F).
לכן נעדכן את המרחק של F ל־11m ואת העדיפות שלו בתור.
מצאנו מסלול קצר יותר ל־F.
אותו הדבר עבור D.
מצאנו מסלול קצר יותר — A → C → D קצר מ־A → B → D.
נעדכן את המרחק מ־22m ל־20m.
כל שכניו של C נבדקו, ולכן נוסיף את C ל־visited.
נשלוף מהתור את הצומת הקרוב ביותר הבא — F.
נרשום את המרחק ל־E כ־11m + 9m = 20m.
נוסיף את F לקבוצת visited, ונשלוף את הצומת הקרוב הבא — D.
המרחק ל־E דרך D הוא 20m + 6m = 26m.
זה ארוך יותר מהמרחק שכבר חושב (20m דרך F), ולכן נתעלם ממנו.
הצומת D כעת סומן כ"ביקור הושלם".
הצומת E גם סומן כ"ביקור הושלם".
סיימנו את המעבר בגרף.
כעת אנו יודעים את המרחקים הקצרים ביותר מכל צומת לנקודת ההתחלה A.
בפועל, במהלך חישוב המרחקים שומרים גם את ה־previousVertices (הצמתים הקודמים)
כדי שנוכל לשחזר את הרצף המדויק של הצמתים שמרכיבים את המסלול הקצר ביותר.
לדוגמה, המסלול הקצר מ־A ל־E הוא A → C → F → E.