42. خوارزمية Dijkstra's: مقدمة والجشع (Greediness)

تحل خوارزمية Dijkstra's مشكلة أقصر مسار لمصدر واحد (single-source) للرسم البياني المُوزَّن ذي الأوزان غير السالبة للحواف.

المفهوم الأساسي: النهج الجشع (Greedy Approach)

Dijkstra's هي خوارزمية جشعة (Greedy Algorithm). في كل خطوة، تتخذ الخيار الذي يبدو الأفضل في الوقت الحالي، على أمل أن يؤدي هذا الأمثل المحلي إلى أمثل عالمي.

1. البدء من عُقدة المصدر، مع تحديد مسافتها إلى 0 وجميع المسافات الأخرى إلى ما لا نهاية.
2. تحديد العُقدة غير المُزارة التي لديها حالياً أصغر مسافة معروفة من المصدر بشكل متكرر.
3. 'زيارة' تلك العُقدة وتحديث مسافات جميع جيرانها.

متطلبات هيكل البيانات

تستخدم Dijkstra's Min Heap (قائمة انتظار ذات أولوية) للعثور بكفاءة على العُقدة غير المُزارة ذات المسافة الأصغر في زمن قدره O(log N)، مما يجعل التعقيد العام فعالاً للغاية.