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