Time and Space Complexity

التعقيد الزمني:

• O(V² + V*E) كما هو مكتوب هنا (كل جولة من جولات V تمسح الرؤوس للعثور على الحد الأدنى وتمسح الحواف للاسترخاء). مع الكومة الثنائية (binary heap) وقائمة الجوار (adjacency list)، يتحسن التعقيد إلى O((V + E) log V).

التعقيد المكاني:

• O(V) لمصفوفات المسافة (distance) والزيارة (visited) (بالإضافة إلى حواف الإدخال).

ملخص:

• تجد خوارزمية ديكسترا (Dijkstra) أقصر المسافات من مصدر واحد للأوزان غير السالبة عن طريق إنهاء أقرب رأس بشكل جشع واسترخاء حوافه.
• لا تعمل الخوارزمية مع الحواف السالبة؛ استخدم خوارزمية بلمان-فورد (Bellman-Ford) لتلك الحالات.