خوارزمية ديكسترا
- قدّمه
- Edsger W. Dijkstra
- السنة
- 1956
- النوع
- algorithm
- العائلة
- Graph Algorithms
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
خوارزمية ديكسترا، التي قدمها إدزجر دبليو ديكسترا في عام 1956، هي واحدة من أهم الخوارزميات الأساسية في علوم الحاسوب لحل مشكلة أقصر مسار من مصدر واحد. تجد أقصر مسار من رأس البداية إلى جميع الرؤوس الأخرى في رسم بياني موزون بأوزان حواف غير سالبة.
الفكرة الحدسية وراء الطريقة
تحافظ الخوارزمية على مجموعة من الرؤوس التي تم معرفة أقصر مسافاتها من المصدر بالفعل، وتوسع هذه المجموعة بشكل متكرر عن طريق اختيار أقرب رأس غير معالج وتحديث المسافات إلى جيرانه. الفكرة الرئيسية هي الخاصية الجشعة: بمجرد اختيار رأس، تكون مسافته من المصدر نهائية لأن جميع أوزان الحواف غير سالبة، لذا فإن أي مسار أطول عبر رؤوس غير مزورة لا يمكن أن يكون أقصر. هذا يضمن الصحة والأمثلية.
التاريخ
نشر إدزجر دبليو ديكسترا خوارزميته في عام 1959 في ورقة بحثية من ثلاث صفحات أصبحت واحدة من أكثر الأعمال استشهادًا في علوم الحاسوب. نشأت الخوارزمية من عمل ديكسترا على جهاز كمبيوتر ARMAC في أمستردام. على مدى عقود، تم إجراء العديد من التحسينات، بما في ذلك هياكل البيانات الأفضل (كومات فيبوناتشي التي تحقق تعقيد O(E+VlogV)) والمتغيرات ثنائية الاتجاه. تظل الخوارزمية مركزية لبروتوكولات التوجيه الحديثة مثل OSPF في الشبكات.
متى تُستخدم
طبق خوارزمية ديكسترا عند إيجاد أقصر المسارات في الرسوم البيانية ذات أوزان الحواف غير السالبة. إنها مثالية لأنظمة الملاحة، وتوجيه الشبكات، وأي مشكلة رسم بياني تتطلب مسارات مثلى. استخدمها لأقصر المسارات من مصدر واحد إلى جميع الرؤوس. بالنسبة للرسوم البيانية ذات الأوزان السالبة، استخدم خوارزمية بلمان-فورد بدلاً من ذلك. للبحث ثنائي الاتجاه أو التوجيه الاستدلالي، ضع في اعتبارك خوارزمية A*.
الحدود والاعتبارات
- لا يمكنها التعامل مع الرسوم البيانية ذات أوزان الحواف السالبة
- تحسب أقصر المسارات إلى جميع الرؤوس، وليس فقط وجهة واحدة (على الرغم من أنه يمكن إنهاؤها مبكرًا)
- أقل كفاءة من A* عندما تكون المعلومات الاستدلالية متاحة
- تتطلب اكتشاف جميع الرؤوس؛ غير فعالة للاتصال المتناثر جدًا
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- سهلة الفهم والتنفيذ مع ضمانات صحة واضحة
- فعالة مع هياكل البيانات المناسبة: O((V+E)logV) مع كومة ثنائية، O(V²) مع مصفوفة
- مثالية للرسوم البيانية ذات الأوزان غير السالبة؛ تثبت أمثلية المسارات المحسوبة
- تعمل على الرسوم البيانية الموجهة وغير الموجهة
- أساس للعديد من التوسعات والخوارزميات ذات الصلة
التطبيقات
- أنظمة تحديد المواقع العالمي (GPS) وأنظمة الملاحة: إيجاد أقصر المسارات للمركبات والمشاة
- بروتوكولات توجيه الشبكات: تحديد المسارات المثلى لحزم البيانات في شبكات الكمبيوتر
- الشبكات الاجتماعية: إيجاد أقصر مسارات الاتصال بين المستخدمين أو المؤثرين
- تطوير الألعاب: إيجاد المسارات للذكاء الاصطناعي وحركة الشخصيات غير اللاعبة
- تخطيط حركة الروبوتات: حساب المسارات المثلى للأنظمة الروبوتية
- الاتصالات: تحسين توجيه المكالمات ومسارات انتشار الإشارات
كيف يعمل
كيف يعمل
عيّن المسافة إلى المصدر بصفر وجميع المسافات الأخرى إلى ما لا نهاية. ضع علامة على جميع الرؤوس بأنها غير مزورة وأنشئ طابور أولوية.
اختر الرأس غير المزورة ذي المسافة الدنيا من المصدر باستخدام طابور الأولوية.
لكل جار للرأس المختار، إذا كان المسار عبر الرأس المختار يوفر مسافة أقصر، قم بتحديث مسافة الجار وأضفه إلى طابور الأولوية.
الأخطاء الشائعة
- استخدام الخوارزمية على الرسوم البيانية ذات الأوزان السالبة، مما يؤدي إلى أقصر المسارات غير الصحيحة
- تنفيذ غير فعال مع عملية استخراج الحد الأدنى في زمن خطي، مما يؤدي إلى أداء ضعيف
- الفشل في تحديث المسافات بشكل صحيح عند إعادة زيارة الجيران عبر مسارات مختلفة
الأسئلة الشائعة
لماذا تفشل خوارزمية ديكسترا على الأوزان السالبة؟
تفترض الخوارزمية أنه بمجرد الانتهاء من رأس، لا يمكن العثور على مسار أقصر عبر الرؤوس غير المزورة. مع الأوزان السالبة، قد يتحسن مسار أطول لاحقًا عند استخدام حافة سالبة، مما ينتهك هذا الافتراض.
ما هي بنية البيانات التي يجب استخدامها لطابور الأولوية؟
توفر الكومات الثنائية عمليات O(logV) لكل من الإدراج والاستخراج، مما يؤدي إلى تعقيد إجمالي O((V+E)logV). تحقق كومات فيبوناتشي O(E+VlogV) ولكن لها عوامل ثابتة كبيرة. تعمل المصفوفات بشكل جيد للرسوم البيانية الصغيرة.
كيف يمكن لخوارزمية ديكسترا إيجاد المسار إلى وجهة محددة؟
أنهِ الخوارزمية بمجرد اختيار رأس الوجهة (يتم الانتهاء من مسافته)، وتجنب الحسابات غير الضرورية. بدلاً من ذلك، أعد بناء المسار عن طريق الاحتفاظ بمؤشرات الآباء أثناء التنفيذ.
هل يمكن استخدام خوارزمية ديكسترا في الرسوم البيانية غير الموجهة؟
نعم، يمكن تمثيل الرسوم البيانية غير الموجهة كرسوم بيانية موجهة مع حواف في كلا الاتجاهين لكل حافة غير موجهة، ولكل منها نفس الوزن. تعمل الخوارزمية بشكل متطابق على التمثيل ثنائي الاتجاه.
طرق ذات صلة
المصادر
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
افتح مرجع DOIتم النسخ.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ردمك: 978-0-262-03384-8تم النسخ.