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

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

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

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

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

הזמן הכולל תלוי במימוש תור הקדימויות. מימוש פשוט כרשימה נותן זמן O(V^2). שימוש בערימה בינארית נותן O(E log V). קיימות ערימות מתוחכמות יותר (כמו ערימת פיבונאצ'י) שמקטינות את הזמן התיאורטי, אך הן מורכבות יותר למימוש ופחות נפוצות בפרקטיקה.

קיימות שדרוגים שימושיים: דייקסטרה דו‑כיווני מריץ חיפוש מהמקור ומהיעד בו זמנית. אלגוריתם A* מוסיף פונקציית יוריסטיקה (הערכה של המרחק שנותר) כדי לכוון את החיפוש ולסרוק פחות קודקודים. יש גם אופטימיזציות מיוחדות לרשתות כבישים, כמו transit node routing, שמבצעות חישוב מקדים כדי לזרז שאילתות רבות.

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

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

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

דייקסטרה הוא כלי למציאת הדרך הקצרה במפה שמחוברת בנקודות וקווים. נקודות נקראות קודקודים. קווים נקראים קשתות.

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

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

אם יש קווים עם "משקל" שלילי, לא תמיד יעבוד טוב. משקל שלילי הוא ערך שמקטין את העלות.

משתמשים בזה במפות, באינטרנט ובאפליקציות ניווט כדי למצוא דרכים טובות.

דייקסטרה הומצא בשנות ה־50 על ידי אדסחר דייקסטרה.

במשפטים קצרים: דייקסטרה מוצא את הדרך הקצרה ברשת נקודות וקווים, כשהעלות של כל קו אינה שלילית.