خوارزمية ديكسترا

خوارزمية ديكسترا ( تُلفظ /ˈdaɪk.strəz/ ، دايك - سترز ) هي خوارزمية لإيجاد أقصر المسارات بين العقد في رسم بياني مُثقَّل، والذي قد يُمثِّل ، على سبيل المثال، شبكة طرق . ابتكرها عالم الحاسوب إدسكار دبليو ديكسترا عام 1956 ونُشرت بعد ثلاث سنوات. ^{[ 4 ] [ 5 ] [ 6 ]}

تُحدد خوارزمية ديكسترا أقصر مسار من عقدة مصدر معينة إلى جميع العقد الأخرى. ^{[ 7 ] : 196-206.} ويمكن استخدامها لإيجاد أقصر مسار إلى عقدة وجهة محددة، وذلك بإنهاء الخوارزمية بعد تحديد أقصر مسار إلى تلك العقدة. على سبيل المثال، إذا كانت عقد الرسم البياني تُمثل مدنًا، وكانت تكاليف الحواف تُمثل المسافات بين أزواج المدن المتصلة بطريق مباشر، فيمكن استخدام خوارزمية ديكسترا لإيجاد أقصر مسار بين مدينة واحدة وجميع المدن الأخرى. من التطبيقات الشائعة لخوارزميات أقصر مسار بروتوكولات توجيه الشبكات ، وأبرزها بروتوكول IS-IS (النظام الوسيط إلى النظام الوسيط) وبروتوكول OSPF (فتح أقصر مسار أولًا). كما تُستخدم أيضًا كإجراء فرعي في خوارزميات أخرى مثل خوارزمية جونسون .

تستخدم الخوارزمية بنية بيانات قائمة انتظار ذات أولوية دنيا لاختيار أقصر المسارات المعروفة حتى الآن. قبل اكتشاف هياكل قوائم الانتظار ذات الأولوية الأكثر تطورًا، كانت خوارزمية ديكسترا الأصلية تعمل في${\displaystyle \ثيتا (|V|^{2})}$الوقت ، أين${\displaystyle |V|}$يمثل عدد العقد. ^{[ 8 ] [ 9 ]} اقترح فريدمان وتارجان (1984) طابور أولوية كومة فيبوناتشي لتحسين تعقيد وقت التشغيل إلى${\displaystyle \Theta (|E|+|V|\log |V|)}$، أين${\displaystyle |E|}$يمثل عدد الحواف. تُعد هذه الخوارزمية، من الناحية التقاربية، الأسرع المعروفة لإيجاد أقصر مسار من مصدر واحد للرسوم البيانية الموجهة ذات الأوزان غير السالبة وغير المحدودة. مع ذلك، يمكن تحسين الحالات الخاصة (مثل الأوزان المحدودة/الصحيحة، والرسوم البيانية الموجهة غير الدورية، إلخ) بشكل أكبر . في حال السماح بالمعالجة المسبقة، يمكن أن تكون خوارزميات مثل التسلسلات الهرمية الانكماشية أسرع بما يصل إلى سبعة أضعاف .

تُستخدم خوارزمية ديكسترا عادةً على الرسوم البيانية التي تكون فيها أوزان الحواف أعدادًا صحيحة موجبة أو أعدادًا حقيقية. ويمكن تعميمها على أي رسم بياني تكون فيه أوزان الحواف مرتبة جزئيًا ، بشرط أن تكون التسميات اللاحقة (يتم إنتاج تسمية لاحقة عند اجتياز حافة) غير متناقصة بشكل رتيب . ^{[ 10 ] [ 11 ]}

في العديد من المجالات، وخاصة الذكاء الاصطناعي ، تقدم خوارزمية ديكسترا أو أحد متغيراتها بحثًا بتكلفة موحدة ، ويتم صياغتها كمثال على الفكرة الأكثر عمومية للبحث الأفضل أولاً . ^{[ 12 ]}

ما هو أقصر طريق للسفر من روتردام إلى جرونينجن ، بشكل عام: من مدينة معينة إلى مدينة معينة؟ إنها خوارزمية أقصر مسار ، صممتها في حوالي عشرين دقيقة. في صباح أحد الأيام، كنت أتسوق في أمستردام مع خطيبتي الشابة، وكنا متعبين، فجلسنا على شرفة المقهى لنحتسي فنجان قهوة، وكنت أفكر فيما إذا كان بإمكاني فعل ذلك، فصممت خوارزمية أقصر مسار. كما قلت، كان ابتكارًا استغرق عشرين دقيقة. في الواقع، نُشرت الخوارزمية عام 1959، بعد ثلاث سنوات. لا يزال المنشور مقروءًا، وهو في الحقيقة جميل جدًا. أحد أسباب جماله هو أنني صممته دون استخدام قلم وورقة. علمت لاحقًا أن إحدى مزايا التصميم دون قلم وورقة هي أنك تُجبر تقريبًا على تجنب كل التعقيدات التي يمكن تجنبها. في النهاية، أصبحت تلك الخوارزمية، لدهشتي الكبيرة، إحدى ركائز شهرتي.

فكّر ديكسترا في مسألة أقصر مسار أثناء عمله كمبرمج في المركز الرياضي بأمستردام عام ١٩٥٦. أراد أن يُظهر قدرات حاسوب ARMAC الجديد. ^{[ ١٣ ]} كان هدفه اختيار مسألة وحل حاسوبي يُمكن لغير المتخصصين في الحوسبة فهمهما. صمّم خوارزمية أقصر مسار، ثم طبّقها لاحقًا على ARMAC لخريطة نقل مُبسّطة قليلاً لـ ٦٤ مدينة في هولندا (حدّدها بـ ٦٤ مدينة، بحيث تكفي ٦ بتات لترميز رقم المدينة). ^{[ ٥ ]} بعد عام، صادف مسألة أخرى طرحها مهندسو الأجهزة العاملون على حاسوب المعهد التالي: تقليل كمية الأسلاك اللازمة لتوصيل دبابيس اللوحة الخلفية للجهاز. كحل، أعاد اكتشاف خوارزمية الشجرة الممتدة الدنيا لبريم (المعروفة سابقًا ليارنيك ، والتي أعاد بريم اكتشافها أيضًا ). ^{[ 14 ] [ 15 ]} نشر ديكسترا الخوارزمية في عام 1959، بعد عامين من بريم و29 عامًا من جارنيك. ^{[ 16 ] [ 17 ]}

تتطلب الخوارزمية عقدة بداية، وتحسب أقصر مسافة من تلك العقدة إلى كل عقدة أخرى. تبدأ خوارزمية ديكسترا بمسافات لا نهائية وتحاول تحسينها خطوة بخطوة.

1. أنشئ مجموعة من جميع العقد التي لم تتم زيارتها: مجموعة العقد التي لم تتم زيارتها.
2. يُخصص لكل عقدة قيمة مسافة من نقطة البداية: بالنسبة لعقدة البداية، تكون المسافة صفرًا، وبالنسبة لجميع العقد الأخرى، تكون المسافة ما لا نهاية، نظرًا لعدم وجود مسار معروف لهذه العقد في البداية. أثناء التنفيذ، تكون مسافة العقدة N هي طول أقصر مسار تم اكتشافه حتى الآن بين عقدة البداية ^و N. ^{[ 18} ]
3. من مجموعة العقد غير المزارة، يتم اختيار العقدة الحالية لتكون ذات أقصر مسافة (محدودة)؛ في البداية، تكون هذه هي عقدة البداية (مسافة صفر). إذا كانت مجموعة العقد غير المزارة فارغة، أو تحتوي فقط على عقد ذات مسافة لا نهائية (غير قابلة للوصول)، فإن الخوارزمية تتوقف بالانتقال إلى الخطوة 6. إذا كان الهدف الوحيد هو الوصول إلى عقدة مستهدفة، فإن الخوارزمية تتوقف بمجرد أن تصبح العقدة الحالية هي العقدة المستهدفة. وإلا، تستمر الخوارزمية.
4. بالنسبة للعقدة الحالية، ضع في اعتبارك جميع جيرانها الذين لم تتم زيارتهم، وقم بتحديث المسافات بينهم عبر العقدة الحالية؛ قارن المسافة المحسوبة حديثًا بالمسافة المُخصصة حاليًا للجيران، ثم خصص المسافة الأقصر للجيران. على سبيل المثال، إذا كانت العقدة الحالية A مُحددة بمسافة 6، وكان طول الحافة التي تربطها بجارتها B هو 2، فإن المسافة إلى B عبر A هي 6 + 2 = 8. إذا كانت B مُحددة سابقًا بمسافة أكبر من 8، فقم بتحديثها إلى 8 (المسار إلى B عبر A أقصر). وإلا، فاحتفظ بمسافتها الحالية (المسار إلى B عبر A ليس الأقصر).
5. بعد النظر في جميع جيران العقدة الحالية الذين لم تتم زيارتهم، تُزال العقدة الحالية من مجموعة العقد غير المُزارة. وبالتالي، لا يُعاد فحص العقدة التي تمت زيارتها، وهذا صحيح لأن المسافة المُسجلة على العقدة الحالية هي الحد الأدنى (كما تم التأكد منه في الخطوة 3)، وبالتالي فهي نهائية. كرر الخطوات من الخطوة 3.
6. بمجرد خروج الحلقة (الخطوات 3-5)، تحتوي كل عقدة تمت زيارتها على أقصر مسافة لها من عقدة البداية.

يمكن إيجاد أقصر مسار بين تقاطعين على خريطة مدينة باستخدام هذه الخوارزمية بقلم وورقة. يُدرج كل تقاطع على سطر منفصل: أحدهما نقطة البداية ويُرمز له بالمسافة 0. أما باقي التقاطعات، فتُرمز لها في البداية بالمسافة اللانهائية. يُقصد بذلك الإشارة إلى أنه لم يتم تحديد مسار إلى هذه التقاطعات بعد. في كل تكرار، يصبح أحد التقاطعين هو التقاطع الحالي. في التكرار الأول، يكون هذا التقاطع هو نقطة البداية.

انطلاقًا من التقاطع الحالي، تُحسب المسافة إلى كل تقاطع مجاور (متصل مباشرةً) بجمع قيمة (تصنيف) التقاطع الحالي مع المسافة إلى التقاطع المجاور، ثم يُعاد تصنيف التقاطع المجاور بالقيمة الأقل بين المجموع وتصنيفه الحالي. أي، يُعاد تصنيف التقاطع المجاور إذا كان المسار إليه عبر التقاطع الحالي أقصر من المسارات التي حُسبت سابقًا. في هذه الحالة، يُشار إلى الطريق المؤدي إلى التقاطع المجاور بسهم، ويُحذف أي سهم آخر يشير إليه. بعد حساب المسافات إلى كل تقاطع مجاور للتقاطع الحالي، يُصنف التقاطع الحالي على أنه تمت زيارته. يصبح التقاطع غير المُزار ذي التصنيف الأصغر هو التقاطع الحالي، وتتكرر العملية حتى تتم زيارة جميع العقد ذات التصنيفات الأقل من تصنيف الوجهة.

بمجرد عدم وجود عقد غير تمت زيارتها تحمل تسمية أصغر من تسمية الوجهة، فإن الأسهم المتبقية تُظهر أقصر مسار.

في الشفرة الزائفة التالية ، يمثل `dist` مصفوفة تحتوي على المسافات الحالية من المصدر إلى الرؤوس الأخرى، أي أن `dist[ u ]` هي المسافة الحالية من المصدر إلى الرأس `u` . تحتوي المصفوفة `prev` على مؤشرات إلى عقد القفزة السابقة على أقصر مسار من المصدر إلى الرأس المحدد (أو، بشكل مكافئ، هي القفزة التالية على المسار من الرأس المحدد إلى المصدر). يبحث الكود `u ← vertex in Q with min dist[u] ` عن الرأس `u` في مجموعة الرؤوس ` Q` الذي له أقل قيمة لـ `dist[ u ]` . تُرجع الدالة `Graph.Distance( u , v ) ` طول الحافة التي تربط (أي المسافة بين) العقدتين المتجاورتين `u` و` v` . يمثل المتغير `alt` في السطر 14 طول المسار من عقدة المصدر إلى العقدة المجاورة `v` إذا كان سيمر عبر `u` . إذا كان هذا المسار أقصر من أقصر مسار مسجل حاليًا لـ `v` ، فسيتم تحديث مسافة ` v` إلى `alt` . ^{[ 7 ]}

دالة واحدة Dijkstra( الرسم البياني ، المصدر ): 2 3 لكل رأس v في Graph.Vertices : 4 مسافة[ v ] ← ما لا نهاية 5 prev[ v ] ← غير مُعرَّف 6 أضف v إلى Q 7 dist[ source ] ← 0 8 9 طالما أن Q ليست فارغة: 10 u ← رأس في Q ذو أقل مسافة dist[u] 11 Q.remove(u) 12 13 لكل حافة (u, v) في الرسم البياني : 14 alt ← dist[ u ] + Graph.Distance( u , v ) 15 إذا كان alt < dist[ v ]: 16 dist[ v ] ← alt 17 prev[ v ] ← u 18 19 إرجاع dist[], prev[]

لإيجاد أقصر مسار بين رأسي المصدر والهدف ، يتوقف البحث بعد السطر 10 إذا كان u = الهدف . ويمكن الحصول على أقصر مسار من المصدر إلى الهدف عن طريق التكرار العكسي.

1 S ← تسلسل فارغ 2 u ← target 3 إذا كانت prev[ u ] معرفة أو u = source : // تابع إذا كان الوصول إلى الرأس ممكنًا 4 بينما u معرفة: // أنشئ أقصر مسار باستخدام المكدس S 5 S.push(u) // ادفع الرأس إلى المكدس 6 u ← prev[ u ] // انتقل من الهدف إلى المصدر

الآن، التسلسل S هو قائمة الرؤوس التي تشكل أحد أقصر المسارات من المصدر إلى الهدف ، أو التسلسل الفارغ إذا لم يكن هناك مسار موجود.

تتمثل إحدى المشكلات الأكثر عمومية في إيجاد جميع أقصر المسارات بين المصدر والهدف (قد يكون هناك عدة مسارات بنفس الطول). عندئذٍ، بدلاً من تخزين عقدة واحدة فقط في كل مدخل من مصفوفة prev[]، يمكن تخزين جميع العقد التي تحقق شرط التخفيف. على سبيل المثال، إذا كانت كل من r والمصدر متصلة بالهدف وتقعان على أقصر مسارين مختلفين عبر الهدف (لأن تكلفة الحافة متساوية في الحالتين)، فسيتم إضافة كل من r والمصدر إلى prev[ target ] . عند اكتمال الخوارزمية، تصف بنية بيانات prev[] رسمًا بيانيًا يمثل مجموعة فرعية من الرسم البياني الأصلي مع إزالة بعض الحواف. وتتمثل خاصيتها الرئيسية في أنه إذا تم تشغيل الخوارزمية بعقدة بداية معينة، فإن كل مسار من تلك العقدة إلى أي عقدة أخرى في الرسم البياني الجديد يمثل أقصر مسار بين تلك العقد، وجميع المسارات بهذا الطول من الرسم البياني الأصلي موجودة في الرسم البياني الجديد. بعد ذلك، لإيجاد جميع أقصر هذه المسارات بين عقدتين معطيتين، يمكن استخدام خوارزمية بحث عن المسار على الرسم البياني الجديد، مثل البحث العميق أولاً .

دالة واحدة Dijkstra( الرسم البياني ، المصدر ): 2 Q ← طابور تخزين أولوية الرأس 3 4 dist[ source ] ← 0 // التهيئة 5 Q .add_with_priority( source , 0) // الأولوية المرتبطة تساوي dist[·] 6 7 لكل رأس v في Graph.Vertices : ٨ إذا كانت v ≠ المصدر ٩ prev[ v ] ← غير مُعرَّف // السلف لـ v ١٠ dist[ v ] ← ما لا نهاية // مسافة غير معروفة من المصدر إلى v 11 Q.add_with_priority(v, INFINITY) 12 13 ١٤ طالما أن Q غير فارغة: // الحلقة الرئيسية ١٥ u ← Q.extract_min () // إزالة أفضل رأس وإرجاعه ١٦ لكل حافة (u, v): // المرور على جميع الجيران v لـ u ١٧ alt ← dist[ u ] + Graph.Distance( u , v ) 18 إذا كان alt < dist[ v ]: 19 prev[ v ] ← u 20 dist[ v ] ← alt 21 Q .decrease_priority( v , alt ) 22 23 return (dist, prev)

لإثبات صحة خوارزمية ديكسترا، يمكن استخدام الاستقراء الرياضي على عدد العقد التي تمت زيارتها. ^{[ 22 ]}

الفرضية الثابتة : لكل عقدة تمت زيارتها v ، فإن هي أقصر مسافة من المصدر إلى v ، ولكل عقدة لم تتم زيارتها u ، فإن هي أقصر مسافة من المصدر إلى u عند المرور عبر العقد التي تمت زيارتها فقط، أو ما لا نهاية إذا لم يكن هناك مسار كهذا. (ملاحظة: لا نفترض أن هي أقصر مسافة فعلية للعقد التي لم تتم زيارتها، بينما هي أقصر مسافة فعلية).dist[v]dist[u]dist[u]dist[v]

يمكن التعبير عن حدود وقت تشغيل خوارزمية ديكسترا على رسم بياني ذي حواف E ورؤوس V كدالة لعدد الحواف، ويرمز لها بـ${\displaystyle |E|}$وعدد الرؤوس، المشار إليه بـ${\displaystyle |V|}$باستخدام ترميز Big-O . يعتمد حد التعقيد بشكل أساسي على بنية البيانات المستخدمة لتمثيل المجموعة Q. في ما يلي، يمكن تبسيط الحدود العليا لأن${\displaystyle |E|}$يكون${\displaystyle O(|V|^{2})}$بالنسبة لأي رسم بياني بسيط، لكن هذا التبسيط يتجاهل حقيقة أنه في بعض المسائل، توجد حدود عليا أخرى على${\displaystyle |E|}$قد يكون ذلك صحيحاً.

بالنسبة لأي بنية بيانات لمجموعة الرؤوس Q ، يكون وقت التشغيل هو: ^{[ 2 ]}

$${\displaystyle \Theta (|E|\cdot T_{\mathrm {dk} }+|V|\cdot T_{\mathrm {em} }),}$$

أين${\displaystyle T_{\mathrm {dk} }}$و${\displaystyle T_{\mathrm {em} }}$تمثل هذه التعقيدات عمليات تقليل المفتاح واستخراج الحد الأدنى في Q ، على التوالي.

تُخزّن أبسط نسخة من خوارزمية ديكسترا مجموعة الرؤوس Q كقائمة مرتبطة أو مصفوفة، والحواف كقائمة مجاورة أو مصفوفة . في هذه الحالة، يكون استخراج الحد الأدنى مجرد بحث خطي عبر جميع الرؤوس في Q ، لذا فإن وقت التشغيل هو${\textstyle \Theta (|E|+|V|^{2})=\Theta (|V|^{2})}$.

بالنسبة للرسوم البيانية المتفرقة ، أي الرسوم البيانية التي تحتوي على عدد أقل بكثير من${\displaystyle |V|^{2}}$يمكن تحسين كفاءة خوارزمية ديكسترا بتخزين الرسم البياني على شكل قوائم تجاور، واستخدام شجرة بحث ثنائية متوازنة ذاتيًا ، أو كومة ثنائية ، أو كومة اقتران ، أو كومة فيبوناتشي ، أو كومة أولوية كطابور أولوية لاستخراج الحد الأدنى بكفاءة. ولتنفيذ خطوات تقليل المفتاح بكفاءة في كومة ثنائية، من الضروري استخدام بنية بيانات مساعدة تربط كل رأس بموقعه في الكومة، وتحديث هذه البنية مع تغير طابور الأولوية Q. أما مع شجرة بحث ثنائية متوازنة ذاتيًا أو كومة ثنائية، فإن الخوارزمية تتطلب${\textstyle \Theta ((|E|+|V|)\log |V|)}$الوقت في أسوأ الحالات؛ بالنسبة للرسوم البيانية المتصلة، يمكن تبسيط هذا الحد الزمني إلى${\textstyle \Theta (|E|\log |V|)}$. تعمل كومة فيبوناتشي على تحسين ذلك إلى${\textstyle \Theta (|E|+|V|\log |V|)}$.

عند استخدام أكوام ثنائية، يكون متوسط ​​تعقيد الوقت أقل من أسوأ الحالات: بافتراض أن تكاليف الحواف تُسحب بشكل مستقل من توزيع احتمالي مشترك ، فإن العدد المتوقع لعمليات إنقاص المفتاح يكون محدودًا بـ${\displaystyle \Theta (|V|\log(|E|/|V|))}$، مما يعطي وقت تشغيل إجمالي قدره ^{[ 7 ] : 199-200}

$${\displaystyle O\left(|E|+|V|\log {\frac {|E|}{|V|}}\log |V|\right).}$$

الإجراء uniform_cost_search(start) هو العقدة ← البداية الحدود ← قائمة انتظار ذات أولوية تحتوي على عقدة فقط مجموعة موسعة ← مجموعة فارغة إذا كانت الحدود فارغة، فقم بإرجاع خطأ . node ← frontier.pop() إذا كانت العقدة تمثل حالة الهدف، فقم بإرجاع الحل (العقدة). expanded.add(node) لكل جار من جيران العقدة n، إذا لم تكن n في المجموعة الموسعة وليست في المجموعة الحدودية، فأضفها إلى المجموعة الحدودية. وإلا ، إذا كانت n في المجموعة الحدودية ذات التكلفة الأعلى، فقم بما يلي: استبدل العقدة الحالية بالعقدة n

خوارزمية ديكسترا ثنائية الاتجاه

خوارزمية دايجسترا ثنائية الاتجاه هي نسخة معدلة من خوارزمية دايجسترا، مصممة لحساب أقصر مسار بكفاءة بين رأس مصدر معين s ورأس هدف t ، بدلاً من حسابه بين جميع الرؤوس. الفكرة الأساسية هي إجراء بحثين متزامنين: أحدهما للأمام من s على الرسم البياني الأصلي، والآخر للخلف من t على الرسم البياني بعد عكس اتجاه الحواف. يحتفظ كل بحث بتقديراته الأولية للمسافة، وقائمة أولوياته، ومجموعة رؤوسه "المستقرة". يتقدم البحثان باتجاه بعضهما البعض ويلتقيان في مكان ما على طول أقصر مسار s–t . ^{[ 27 ]}

يتم الاحتفاظ بمصفوفتين للمسافة: df[v] (المسافة من s إلى v) و db[v] ( _{المسافة} من v إلى t ) ، وتُهيأ قيمهما إلى _∞ باستثناء df [ s ] = 0 و db [ t ] = 0. يحتوي طابوران ذوا أولوية Qf و Qb _{على الرؤوس التي} لم تُعالَج بالكامل بعد، بينما تخزن مجموعتان Sf _و Sb الرؤوس _التي حُدِّدت مسافة أقصر مسار لها في كل اتجاه. يخزن المتغير μ طول أفضل مسار كامل s _– t تم العثور _عليه حتى الآن، وقيمته الابتدائية ∞ .

تقوم الخوارزمية بشكل متكرر باستخراج الرأس ذي المسافة الدنيا من أي طابور يحتوي حاليًا على المفتاح الأصغر، وتخفف حوافها الصادرة (أو الواردة)، وتحدث قيمة μ كلما اكتشفت اتصالًا بين المجموعتين المستقرتين:

${\displaystyle \mu \leftarrow \min(\mu ,\;d_{f}[u]+w(u,x)+d_{b}[x])}$عند إرخاء الحافة${\displaystyle (u,x)}$في البحث الأمامي و${\displaystyle x\in S_{b}}$،

وبشكل متناظر بالنسبة للبحث العكسي.

تتمثل إحدى السمات الرئيسية في شرط التوقف: بمجرد أن يصبح مجموع الحد الأدنى للأولويات الحالية في كلا الطابورين على الأقل μ ، لا يمكن لأي مسار لم يتم تحديده بعد أن يتجاوز μ . عند هذه النقطة، تساوي μ المسافة الحقيقية لأقصر مسار δ( s , t ) ، وينتهي البحث. ^{[ 27 ]}

يتجنب هذا المعيار خطأً شائعاً يتمثل في التوقف بمجرد أن تتلامس الحدود، مما قد يؤدي إلى تجاهل وجود معبر بديل أقصر في مكان آخر.

نظرًا لأن كل عملية بحث لا تحتاج إلا لاستكشاف نصف مساحة البحث تقريبًا في الرسوم البيانية النموذجية، فإن الطريقة ثنائية الاتجاه غالبًا ما تزور عددًا أقل بكثير من الرؤوس وتُقلل عدد الحواف بشكل كبير مقارنةً بطريقة ديكسترا أحادية الاتجاه في استعلامات الأزواج المفردة. في الرسوم البيانية الشبيهة بشبكات الطرق، يمكن أن يكون التوفير هائلاً، حيث يُقلل أحيانًا المنطقة المستكشفة من كرة ضخمة إلى نصفَي كرة أصغر.

تُستخدم هذه الطريقة على نطاق واسع في توجيه المسارات من نقطة إلى نقطة للخرائط وبرامج الملاحة، وتُشكل أساسًا للعديد من تقنيات تسريع الأداء مثل ALT، والتسلسل الهرمي للتقليص، والتوجيه القائم على الوصول. ^{[ 28 ]}

إذا كان المطلوب هو أقصر مسار فعلي (وليس مجرد المسافة)، فيمكن تخزين مؤشرات المسار السابق في كلا البحثين. عندما يتم تحديث μ عبر نقطة تقاطع x ، تسجل الخوارزمية نقطة الالتقاء هذه وتعيد بناء المسار النهائي كمسار أمامي من s إلى x مضافًا إليه المسار الخلفي من x إلى t .

تُظهر الأبحاث النظرية أن النهج ثنائي الاتجاه الأمثل يمكن أن يكون الأمثل على مستوى الحالة، مما يعني أنه لا توجد خوارزمية صحيحة يمكنها تقليل عدد الحواف بشكل مقارب على نفس حالة الرسم البياني. ^{[ 29 ]}

يمكن توسيع خوارزمية ديكسترا الأصلية بإجراء تعديلات عليها. على سبيل المثال، قد يكون من المرغوب فيه أحيانًا عرض حلول أقل من الحل الأمثل رياضيًا. وللحصول على قائمة مرتبة بالحلول الأقل من الأمثل، يُحسب الحل الأمثل أولًا. ثم يُحذف ضلع واحد من أضلاع الحل الأمثل من الرسم البياني، ويُحسب الحل الأمثل لهذا الرسم البياني الجديد. بعد ذلك، يُحذف كل ضلع من أضلاع الحل الأصلي بالتتابع، ويُحسب أقصر مسار جديد. ثم تُرتب الحلول الثانوية وتُعرض بعد الحل الأمثل الأول.

تُعد خوارزمية ديكسترا عادةً المبدأ الأساسي وراء بروتوكولات توجيه حالة الارتباط . ويُعتبر بروتوكولا OSPF و IS-IS الأكثر شيوعًا.

على عكس خوارزمية ديكسترا، يمكن استخدام خوارزمية بيلمان-فورد على الرسوم البيانية ذات أوزان الحواف السالبة، طالما لا يحتوي الرسم البياني على أي دورة سالبة يمكن الوصول إليها من رأس المصدر s . وجود مثل هذه الدورات يعني أنه لا يمكن إيجاد أقصر مسار، لأن قيمة الوسم تصبح أقل في كل مرة يتم فيها اجتياز الدورة. (يفترض هذا البيان أن "المسار" مسموح له بتكرار الرؤوس. في نظرية الرسوم البيانية، هذا غير مسموح به عادةً. في علوم الحاسوب النظرية، يُسمح به غالبًا). من الممكن تكييف خوارزمية ديكسترا للتعامل مع الأوزان السالبة من خلال دمجها مع خوارزمية بيلمان-فورد (لإزالة الحواف السالبة واكتشاف الدورات السالبة): خوارزمية جونسون .

خوارزمية A* هي تعميم لخوارزمية Dijkstra التي تقلل من حجم الرسم البياني الفرعي الذي يجب استكشافه، إذا كانت هناك معلومات إضافية متاحة توفر حدًا أدنى للمسافة إلى الهدف.

تتشابه العملية التي يقوم عليها خوارزمية ديكسترا مع العملية الجشعة المستخدمة في خوارزمية بريم . يهدف بريم إلى إيجاد شجرة ممتدة دنيا تربط جميع العقد في الرسم البياني، بينما يهتم ديكسترا بعقدتين فقط. لا يُقيّم بريم الوزن الإجمالي للمسار من عقدة البداية، بل يُقيّم الحواف الفردية فقط.

يمكن اعتبار البحث بالعرض أولاً حالة خاصة من خوارزمية ديكسترا على الرسوم البيانية غير الموزونة، حيث يتحول طابور الأولوية إلى طابور FIFO .

يمكن اعتبار طريقة المسير السريع بمثابة نسخة مستمرة من خوارزمية ديكسترا التي تحسب المسافة الجيوديسية على شبكة مثلثية.

• خوارزمية البحث A*
• خوارزمية بيلمان-فورد
• أقصر مسار إقليدي
• خوارزمية فلويد-وارشال
• خوارزمية جونسون
• مشكلة المسار الأطول
• خوارزمية أقصر مسار متوازية لجميع الأزواج

• كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2001). “القسم 24.3: خوارزمية ديكسترا”. مقدمة للخوارزميات (  الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل . ص 595 – 601. ISBN  0-262-03293-7.
• ديال، روبرت ب. (1969). "الخوارزمية 360: غابة أقصر مسار مع ترتيب طوبولوجي [ H ] " . اتصالات ACM . 12 (11): 632-633 . doi : 10.1145/363269.363610 . S2CID 6754003 . 
• فريدمان، مايكل لورانس ؛ تارجان، روبرت إي. (1984). أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة . المؤتمر السنوي الخامس والعشرون لأسس علوم الحاسوب. معهد مهندسي الكهرباء والإلكترونيات . الصفحات 338-346 . doi : 10.1109/SFCS.1984.715934 . 
• فريدمان، مايكل لورانس ؛ تارجان، روبرت إي. (1987). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" . مجلة رابطة آلات الحوسبة . 34 (3): 596-615 . doi : 10.1145/28869.28874 . S2CID 7904683 . 
• زان، ف. بنجامين؛ نون، تشارلز إي. (فبراير 1998). "خوارزميات أقصر مسار: تقييم باستخدام شبكات طرق حقيقية". علوم النقل . 32 (1): 65-73 . doi : 10.1287/trsc.32.1.65 . S2CID 14986297 . 
• ليزوريك، م.؛ غراي، ر.س.؛ جونسون، أ.أ.؛ لادو، و.س.؛ ميكر الابن، س.ر.؛ بيتري، ر.م.؛ سيتز، ر.ن. (1957). دراسة تقنيات النمذجة - التقرير السنوي الأول - 6 يونيو 1956 - 1 يوليو 1957 - دراسة لتقنيات النمذجة لأنظمة الاتصالات . كليفلاند، أوهايو: معهد كيس للتكنولوجيا.
• كنوت، دي إي (1977). "تعميم لخوارزمية ديكسترا". رسائل معالجة المعلومات . 6 (1): 1-5 . doi : 10.1016/0020-0190(77)90002-3 .
• أهوجا، رافيندرا ك.؛ ميلهورن، كورت؛ أورلين، جيمس ب.؛ تارجان، روبرت إي. (أبريل 1990). "خوارزميات أسرع لمسألة أقصر مسار" (ملف PDF) . مجلة ACM . 37 (2): 213-223 . doi : 10.1145/77600.77615 . hdl : 1721.1/47994 . S2CID 5499589 . 
• رامان، راجيف (1997). "نتائج حديثة حول مشكلة أقصر المسارات من مصدر واحد" . أخبار SIGACT . 28 (2): 81-87 . doi : 10.1145/261342.261352 . S2CID 18031586 . 
• ثوروب ميكيل (2000). “في قوائم انتظار أولوية ذاكرة الوصول العشوائي”. مجلة SIAM للحوسبة . 30 (1): 86-109 . دوى : 10.1137 / S0097539795288246 . S2CID 5221089 . 
• ثورب، ميكيل (1999). "أقصر المسارات غير الموجهة ذات المصدر الواحد بأوزان صحيحة موجبة في زمن خطي" . مجلة ACM . 46 (3): 362-394 . doi : 10.1145/316542.316548 . S2CID 207654795 . 

• مقابلة تاريخية شفهية مع إدسكار دبليو. ديكسترا ، معهد تشارلز باباج ، جامعة مينيسوتا، مينيابوليس
• تطبيق خوارزمية ديكسترا باستخدام منهجية التطوير القائمة على الاختبار (TDD) ، بقلم روبرت سيسيل مارتن ، مدونة الكود النظيف.