סיבוכיות זמן ומקום

סיבוכיות זמן:

• O(V² + V*E) כפי שנכתב כאן (בכל אחד מ־V הסבבים סורקים את הקודקודים כדי למצוא את הקודקוד בעל הערך המינימלי, וסורקים את הקשתות כדי לבצע הרפיה). בעזרת ערימת מינימום בינארית ורשימת שכנויות, הסיבוכיות משתפרת ל־O((V + E) log V).

סיבוכיות מקום:

• O(V) עבור מערכי המרחקים והקודקודים שבהם כבר ביקרנו (בנוסף לקשתות הקלט).

סיכום:

• Dijkstra מוצא את המרחקים הקצרים ביותר ממקור יחיד עבור משקלים שאינם שליליים, באמצעות בחירה חמדנית של הקודקוד הקרוב ביותר וקיבועו, והרפיית הקשתות שלו.
• האלגוריתם אינו עובד עם קשתות שליליות; עבורן יש להשתמש ב־Bellman-Ford.