نهائية
في الطابور
الحواف المفحوصة

  • الحالية
  • في الطابور
  • نهائية
  • المسار
النقر على عقدة يحدد

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

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

تجد خوارزمية ديكسترا أقصر طريق من البداية إلى كل عقدة أخرى عندما تكون للحواف أطوال، مثل الطرق بين المدن. تتوسع من البداية إلى الخارج، وتأخذ دائمًا أقرب عقدة لم تنتهِ منها بعد. انقر على عقدة لتبدأ منها، واختر هدفًا إن شئت، ثم تقدّم خطوة بخطوة لترى الطابور، وكل مسافة تنخفض كلما ظهر طريق أقصر، وظهور أقصر مسار. اضغط «تشغيل» لمشاهدة البحث، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. انقر على عقدة لتجعلها البداية؛ وحوّل النقر إلى «الهدف» ثم انقر على عقدة أخرى للبحث عن أقصر مسار إليها. الرقم على كل حافة هو طولها، والرقم على كل عقدة هو أقصر مسافة لها حتى الآن، والصف أسفل الرسم البياني هو الطابور، الأقرب أولاً. «رسم بياني جديد» ينشئ رسمًا آخر؛ اختر عدد عقده وحوافه. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.

كيف يعمل

  1. انقر على عقدة لتجعلها البداية. للبحث عن مسار، حوّل النقر إلى «الهدف» ثم انقر على عقدة أخرى.
  2. اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتحرك خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع في البحث.
  3. راقب الطابور أسفل الرسم البياني والمسافة على كل عقدة. «رسم بياني جديد» ينشئ رسمًا آخر لتجربته.

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

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

لماذا تكون أقرب عقدة نهائية

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

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

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

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

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

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

ما الفرق بين ديكسترا وBFS؟

يعدّ البحث بالعرض أولاً الحواف ويستخدم طابورًا عاديًا. أما خوارزمية ديكسترا فتجمع أطوال الحواف وتستخدم طابور أولوية يعطي دائمًا أقرب عقدة. وإذا كان طول كل حافة 1، تجد الاثنتان المسافات نفسها.

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

مع كومة ثنائية كطابور أولوية، يزداد العمل بمقدار (V + E) log V لعدد V من العقد وE من الحواف. ومع كومة فيبوناتشي يكون E + V log V. يحتفظ التطبيق بالطابور كقائمة مرتبة، وهي سهلة العرض وكافية للرسوم البيانية الصغيرة.

هل يُرسل الرسم البياني إلى أي مكان؟

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

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

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

الانتقال إلى المحرر