خوارزمية ديكسترا
تجد أرخص طريق من البداية إلى الهدف. تأخذ دائمًا أرخص مكان ينتظر في طابور الأولوية، فتنتشر التكاليف من البداية كالفيضان.
- الوقت O((V + E) log V)
- الذاكرة O(V)
- تستخدم طابور أولوية
ماذا تعني هذه المصطلحات؟
- التكلفة: ثمن الحركة. في المتاهة تكلف الأرض 1 والوحل 3 والماء 9؛ وفي الرسم البياني هي الرقم على الحافة.
- طابور الأولوية: طابور يمر فيه الأرخص أولًا، لا من وصل أولًا.
- التقدير (h): تخمين للتكلفة المتبقية. تبقى A* دقيقة فقط إذا لم يكن التخمين مرتفعًا أبدًا.
- إرخاء الحافة: التحقق مما إذا كان المرور عبر المكان الحالي يعطي جارًا تكلفة أقل، واعتمادها إن كان كذلك.
- في الطابور
- الحالي
- انتهى
- أرخص طريق
- أرض · 1
- وحل · 3
- ماء · 9
- جدار
جديد: البداية في A1 بتكلفة 0. إنه الوحيد في الطابور.
مفتاح المسافة: تشغيل أو إيقاف مؤقت. السهمان الأيسر والأيمن: خطوة بخطوة. Home وEnd: الانتقال المباشر.
جرّب هذا: اختر المستنقع. أرخص طريق يلتف حول الوحل كله: ضعف عدد حركات الخط المستقيم، ومع ذلك أرخص (34 مقابل 36).
كيف يعمل
يحصل كل مكان على تكلفة: 0 للبداية واللانهاية للباقي. تحتفظ ديكسترا بالأماكن التي وصلت إليها في طابور أولوية وتأخذ دائمًا الأرخص. تصبح تكلفته عندها نهائية، لأن أي طريق آخر إليه سيمر بشيء لا يقل عنه غلاءً. ثم تنظر إلى كل جار: إذا كان المرور عبر المكان الذي أخذته للتو أرخص من تكلفة الجار حتى الآن، يحصل الجار على التكلفة الجديدة ويتذكر من أين جاء. عندما يُؤخذ الهدف، تقود هذه الروابط إلى الخلف عبر أرخص طريق.
متى يكون خيارًا جيدًا
استخدم ديكسترا عندما تختلف تكاليف الحركات ولا تقل أي منها عن الصفر: خرائط الطرق وأجهزة الملاحة، وتوجيه الشبكات، وأرخص رحلات طيران متصلة. إذا كانت كل حركة بالتكلفة نفسها، يعطي BFS الإجابة نفسها بشكل أبسط. مع التكاليف السالبة قد تخطئ ديكسترا؛ ولها خوارزمية بلمان–فورد.