Motivation
الدرس 2 من 9 في دورة خوارزمية Dijkstra's Algorithm - خوارزميات الرسوم البيانية على Coddy.
تقوم خوارزمية ديكسترا (Dijkstra) بتنمية مجموعة من الرؤوس التي أصبحت أقصر مسافة لها معروفة بالفعل. فهي تقوم دائماً بتثبيت أقرب رأس لم يتم تثبيته بعد، ثم تستخدمه لتحسين (تخفيف/relax) المسافات إلى جيرانه.
لماذا نتعلم خوارزمية ديكسترا؟
- في كل مكان: توجيه نظام تحديد المواقع (GPS)، وتوجيه حزم الشبكة، وأي بحث عن المسار الأقل تكلفة.
- خوارزمية جشعة (Greedy) ناجحة: مثال واضح على الاختيار الجشع الذي يعطي النتيجة المثلى بشكل مثبت، طالما أن الأوزان غير سالبة.
- الأساس: تظهر فكرة التخفيف (relaxation) الخاصة بها مرة أخرى في خوارزمية A* وخوارزميات أقصر مسار أخرى.
هام: تفترض خوارزمية ديكسترا عدم وجود أوزان سالبة. الحواف السالبة تتطلب خوارزمية بلمان-فورد (Bellman-Ford)، وهو الدرس القادم.
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
