43. خوارزمية Dijkstra's: خطوات التطبيق المفصلة

دعونا نرسم الخطوات الرسمية لـ Dijkstra's:

1. التهيئة (Initialization): إنشاء مصفوفة مسافة dist (جميعها مضبوطة على ما لا نهاية، المصدر مضبوط على 0) ومجموعة visited (فارغة).
2. إعداد قائمة انتظار ذات أولوية: إدراج عُقدة المصدر (مسافة 0) في Min Heap.
3. التكرار: طالما أن Min Heap ليست فارغة: أ. استخراج العُقدة U ذات المسافة الدنيا (الخطوة الجشعة). ب. إذا تمت معالجة U بالفعل (في مجموعة visited)، فاستمر. ج. وضع علامة على U كمُزارة. د. الاسترخاء (Relaxation): لكل جار V لـ U: * حساب المسافة الجديدة المؤقتة: new_dist = dist[U] + weight(U, V). * إذا كان new_dist < dist[V]، قم بتحديث dist[V] وأدرج/حدّث V في قائمة الانتظار ذات الأولوية.

• التعقيد: مع كومة Fibonacci، O(E + V log V). مع كومة ثنائية قياسية (أكثر شيوعاً)، O((V + E) log V).