تطبيق دياكسترا ألغوريتم: حساب خطى خطوة من أجل تقصي المسارات

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

فهم الغوريتم

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

عملية حساب تدريجي

نفترض أن لدينا رسم بياني مع العقدات ألف وباء وجيم ودال وهاء، والحواف المثقلة التالية:

بدءاً من العقد ألف، ابدئي المسافات: ألف = صفر، آخرون = لا نهاية له، وتذكر جميع العقدات كما لم يُنظر إليها.

المطالعة 1

العقد ألف (الملاحظة صفر) تحديث العقدين المجاورين باء وجيم:

Distance to B: 4 (A + 4), to C: 2 (A + 2). Mark A as visited.

الإرسال 2

اختيار العقد جيم )الوزارة ٢( استكمال الجيران دال وهاء:

Distance to D: 10 (C + 8), to E: 12 (C + 10). Mark C as visited.

المصعد 3

اختيار العقد باء )الملاحظة ٤( - استكمال الجيران دال:

المسافة إلى دي: 9 (B + 5) وهو أقل من 10:

الإرسال 4

العقد دال (الملاحظة 9) - تحديث الجيران هاء:

المسافة إلى (إي) 11 (د + 2) تحديث المسافة إلى 11 مارك دي) كما زارها

المصعد 5

(مارك إ) كما زارنا، أقصر طريق من (أ) إلى (هاء) هو عبر الندوات (ج) و (ب) و (د) و (هاء) من مسافة 11