מוטיבציה

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

למה ללמוד את דייקסטרה?

• בכל מקום: ניווט GPS, ניתוב מנות ברשת וכל חיפוש אחר נתיב בעל העלות הנמוכה ביותר.
• חמדני שעובד: דוגמה ברורה לבחירה חמדנית שמוכח כי היא מניבה את הפתרון האופטימלי, כל עוד המשקלים אינם שליליים.
• יסודות: רעיון ההרפיה שלו מופיע שוב ב-A* ובאלגוריתמים אחרים למציאת הנתיב הקצר ביותר.

חשוב: דייקסטרה מניח שאין משקלים שליליים. עבור קשתות שליליות צריך להשתמש ב-Bellman-Ford, הקורס הבא.