ابحث عن أقصر مسار بين نقطتين على الرسم البياني باستخدام خوارزمية Dijkstra

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

الرسم البياني عبارة عن سلسلة من العقد المتصلة بواسطة الحواف. يمكن ترجيح الرسوم البيانية (الحواف تحمل القيم) والاتجاه (الحواف لها اتجاه).

بعض تطبيقات ذلك هي تحسين مسار الرحلة أو 6 درجات من Kevin Bacon.

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

الحل الأكثر شيوعًا لهذه المشكلة هو خوارزمية Dijkstra التي تقوم بتحديث أقصر مسار بين العقدة الحالية وجميع جيرانها.

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

صورة مستويات الكود

الخطوة 0:

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

دعنا نضبط القيمة في كل عقدة على ما لا نهاية موجب ، ونضبط القيمة في عقدة البداية على الصفر.

الخطوة 1:

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

سجل هذه المسافات على العقدة - الكتابة فوق اللانهاية - واقطع العقد أيضًا ، مما يعني أنه تم العثور على أقصر مسار لها.

الخطوة 2:

حدد إحدى العقد التي تم حساب أقصر مسار لها ، وسنسمي هذا المحور الخاص بنا. انظر إلى العقد المجاورة لها (سنسميها عقدنا الوجهة) والمسافات التي تفصل بينها.

لكل عقدة وجهة:

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

الخطوه 3:

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

معلومات اكثر:

المزيد عن خوارزمية Dijkstra

خوارزميات أقصر مسار أخرى