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

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

رسم بياني لحوافه أطوال، تظهر فيه العقد المنتهية القريبة من البداية باللون الأخضر، وشجرة من أقصر الطرق، وطابور أولوية مرسوم أسفله
رسم بياني لحوافه أطوال، تظهر فيه العقد المنتهية القريبة من البداية باللون الأخضر، وشجرة من أقصر الطرق، وطابور أولوية مرسوم أسفله

الفكرة

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

خطوة بخطوة

أعطِ البداية المسافة 0 وكل عقدة أخرى ما لا نهاية. ضع البداية في طابور أولوية، وهو طابور يعطي دائمًا العقدة ذات أصغر مسافة. خذ تلك العقدة؛ فمسافتها الآن نهائية. لكل جار ليس نهائيًا، احسب المسافة عبر هذه العقدة: مسافتها زائد طول الحافة. إذا كانت أقصر من مسافة الجار حتى الآن، فاخفضها، واحفظ هذه العقدة على أنها الطريق إليه، وضع الجار في الطابور. يُسمّى هذا إرخاء الحافة. كرّر حتى يفرغ الطابور، أو حتى يُؤخذ الهدف منه.

مثال

خذ الحواف A–B بطول 4، وA–C بطول 1، وB–C بطول 2، وB–D بطول 1، وC–D بطول 5، وD–E بطول 3، وابدأ من A. أخذ A يعطي B المسافة 4 وC المسافة 1. C هي الأقرب، فتصبح نهائية عند 1؛ وعبر C تنخفض B إلى 1 + 2 = 3 وتحصل D على 1 + 5 = 6. الآن B هي الأقرب، نهائية عند 3، وعبر B تنخفض D إلى 3 + 1 = 4. تصبح D نهائية عند 4 وتعطي E القيمة 4 + 3 = 7. إذن أقصر طريق من A إلى E هو A → C → B → D → E بطول 7، مع أن A → B → D → E يستخدم حوافّ أقل وطوله 8.

لماذا هي صحيحة

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

التاريخ والاستخدامات

صمّم إدسخر و. ديكسترا الخوارزمية عام 1956 لاستعراض حاسوب جديد، هو ARMAC في أمستردام، بإيجاد طرق بين مدن هولندية، ونشرها عام 1959. والفكرة نفسها، مع طابور أذكى، تعمل في تطبيقات الملاحة وفي بروتوكولات توجيه الإنترنت مثل OSPF وIS-IS، التي تحسب أقصر طريق تسلكه البيانات بين أجهزة التوجيه. ويضيف بحث A* تقديرًا للمسافة المتبقية، فيستطيع التوجه نحو الهدف والنظر في عقد أقل.

إدسخر ديكسترا أمام السبورة
إدسخر ديكسترا أمام السبورة

استكشفها

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

الأسئلة المتداولة

ما التعقيد الزمني لخوارزمية ديكسترا؟

يعتمد على طابور الأولوية. مع قائمة بسيطة يكون O(V²) لعدد V من العقد؛ ومع كومة ثنائية O((V + E) log V) لعدد E من الحواف؛ ومع كومة فيبوناتشي O(E + V log V)، كما بيّن مايكل فريدمان وروبرت تارجان عام 1984.

هل تتعامل خوارزمية ديكسترا مع أوزان الحواف السالبة؟

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

هل تجد خوارزمية ديكسترا المسار إلى كل عقدة؟

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

ما علاقة خوارزمية ديكسترا ببحث A*؟

بحث A* هو خوارزمية ديكسترا مع تلميح: فهو يرتب الطابور حسب المسافة حتى الآن زائد تقدير للمسافة المتبقية، مثل المسافة في خط مستقيم على الخريطة. ومع تقدير جيد يجد المسار الأقصر نفسه وهو ينظر في عقد أقل بكثير.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

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