المخططات الموزونة وأقصر مسار – خوارزمية ديكسترا

ماذا تعرض

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

طريقة الاستخدام

اختر «الخريطة»، ثم حدد البداية والوجهة في «من» و«إلى». اضغط «الخطوة التالية ◀» مرارًا واطلب من الطلاب توقّع الرأس الذي سيُثبَّت تاليًا والوسوم التي ستتغير؛ واستخدم «▶ الخطوة السابقة» للعودة إلى قرار سابق. قارن المسار النهائي بالمسار الذي يمر بأقل عدد من الطرق. ثم اضبط «النقر على ضلع» على «يغلق / يفتح الطريق»، وأغلق طريقًا على أقصر مسار، واضغط «تشغيل الكل» لترى المسار الجديد.

المعاملات القابلة للتغيير

• الخريطة بلدة (7 مواقع), مناطق محافظة (9 مواقع)
• رأس البداية
• رأس النهاية

أسئلة للاستكشاف

1. لماذا لا يتغير وسم الرأس أبدًا بعد تثبيته؟
2. هل المسار الذي يمر بأقل عدد من الأضلاع هو الأقصر دائمًا، وأي مثال على الخريطة يبيّن ذلك؟
3. أي الطرق يمكنك إغلاقها بحيث تبقى الطرق الباقية مترابطة ويكون للمخطط دارة أويلر؟