المسرد · approach
Dijkstra Algorithm
خوارزمية كثيرة الحدود لـEdsger Dijkstra (1959) للمسارات الأقصر من مصدر واحد على رسوم بأوزان حواف غير سالبة؛ جشِعة — تستخرج العقدة غير المزارة ذات أصغر مسافة مؤقّتة من قائمة أولوية وتُرَخّي جيرانها؛ O((V+E) log V) مع binary heap.
خوارزمية DijkstraDijkstraخوارزمية ديكستراDijkstra Shortest Path
خوارزمية Dijkstra هي الخوارزمية كثيرة الحدود التي عرّفها Edsger Dijkstra في ورقته من صفحتين عام 1959 في *Numerische Mathematik*؛ تحلّ مسألة المسار الأقصر من مصدر واحد (أقصر مسار من عقدة مصدر إلى كلّ العُقد الأخرى) على رسم بأوزان حواف غير سالبة. نهج جشِع: في كلّ خطوة، استخراج العقدة غير المزارة ذات أصغر مسافة مؤقّتة من قائمة أولوية، وترخية (تحديث) مسافات جيرانها. التعقيد: O((V+E) log V) مع binary heap، O(E + V log V) مع Fibonacci heap. في صيغة single-source single-destination يتوقّف البحث حين الوصول إلى الهدف؛ في single-source all-destinations يُعالَج الرسم بأكمله. تأسيسية؛ روتين فرعي في أنظمة عملية لا تُحصى (بروتوكولات التوجيه OSPF، الملاحة، المسافة في الشبكات الاجتماعية، تحويل الحزم). A* (Hart-Nilsson-Raphael 1968) متغيّر Dijkstra الموجَّه بالاستدلال؛ contraction hierarchies (Geisberger 2008) الامتداد الحديث القائم على المعالجة المسبقة لشبكات الطرق الوطنية. عند وجود حواف سالبة لا يكون Dijkstra أمثل — يلزم Bellman-Ford. Cormen-Leiserson-Rivest-Stein (2009) *Introduction to Algorithms* المرجع التعليمي.
Örnek
في عملية خدمة ميدانية، يُحسَب أقصر مسار زمنيًّا من العميل 1 إلى العميل 12 في ميلّيثوانٍ على رسم شبكة الطرق الحضرية بـDijkstra القائم على binary heap؛ يحدّد مركز الإرسال أقرب فنّيّ لمكالمة طوارئ واردة بمتغيّر Dijkstra من نوع single-source all-destinations.