أقصر الطرق من النقطة A إلى النقطة B, نظرة على خوارزمية ديجيكسترا

في هذا الدرس إن شاء الله سنتناول من أهم المفاهيم المستعملة في علوم البرمجيات وهي خوارزمية أقصر الطرق

سأحاول عن أضع مقدمة نضرية ومن ثم أدعمها بأمثلة ومن ثم أضع الكود
بسم الله نبدأ
نفرض مثلا أنك تريد ان تذهب من مكان إلى مكان آخر و ليس لديك الوقت الكافي فماذا ستفعل ؟؟؟
بالطبع ستسلك أقرب طريق من المكان الذي انت موجود فيه إلى المكان الذي تريد الذهاب إليه فكيف عرفت أن ذلك الطريق هو أقصر طريق ؟؟
قد تبدوا الإجابة سهلة : فالإجابة المنطقية هي أنني أعرف أن المسافة التي سلكتها هي أقصر مسافة عن الطرق الأخرى
هذا من أرض الواقع
لنفرض مثلا أنك تبرمج لعبة وفي إحدى المراحل تطلب الأمر ان تجد اقرب مسافة لتكون مسار الرصاصة او المسار الذي سيسلكه اللاعب
مثال آخر إفرض أن لديك خارطة وتريد أن تعرف اقرب مسافة بين مدينتين على أن تضع المسافة بين التقاطعات
فكيف ستجد أقصر الطريق
الجواب نجده عند خوارزمية ديجيكسترا
خوارزمية ديجيكسترا هي من أشهر الخوارزميات بالطبع توجد هوارزميات أخرى مثل خوارزمية فورد وبيولمان و...
لكن ديجيكسترا من أشهرهم
أولا تعتمد هذه الخوارزمية ان يكون اولا هناك جراف ( رسم مبياني ) (آسف لا أعرف التسمية العربية الدقيقة ) وهذا الجراف يجب أن يختوى على عقدة و ونقطة الوصول وعلى ان يكون الجراف موجه وان تكون المسافة معروفة بين كل عقدة

مثال

في هذا الشكل نرى هناك 5 عقد والدوائر التي وضعتها على رؤوس الأسهم لتبين ان الجراف موجه
إذن كيف سنعرف أقصر مسافة بين العقدة A والعقد D و C
سأشرح الخوارزمية مع المثال
في الشكل أعلاه نريد حساب أقرب مسافة بين A وD و C
سأضع جدول يشرح حالة الجراف في حالته البدئية

في الجدول نرى ان العقدة A فيها 0 لأنها العقدة التي فيها أقصر مسافة وتحت الصفر نلاحظ وجود نقطة سوداء كبيرة للدلالة على ان هذه العقدة هي التي سننطلق منها للعقد لآخرى لأنها تحتوي على أقل رقم .
رمز الانهاية للدلالة على اننا لا نعرف المسافة الفاصلة بين العقدة A والعقد الأخرى

ننطلق من العقدة A
العقدة A إلى أي من العقد تصب إنها تصب في العقدتين B و E
نرى ان المسافة التي بين العقدة A و B هي : 10
والمسافة التي بين العقدة A و E هي : 5

في هذه الصورة وضحت المسارين بلون مختلف

إذن أقصر المسافة بين العقدتين هي : 5

هذا الجدول يبين ذلك

نلاحظ في الجدول أننا وضعنا الرقم 10 تحت العقدة B وبالقرب من 10 وضعنا الحرف A ليدل على أن المسار آت من العقدة A
وتحت العقدة E وضعنا الرقم 5 بإطار لنبين ان الرقم 5 هو المسار الأقصر من العقدة A وبين العقدتين B و E

بما اننا وجدنا ان العق دة E فيها أقل رثم نبدا منها لهذا في الجدول الأخير وتحت الرقم 5 وضعت نقط سوداء للدلالة على اننا سوف نبدأ منها
إذن نذهب إلى العقدة E
نرى ان العقدة E تؤدي إلى كل من العقد B و C و D
لنرى الصورة التبيانية لحالة العقد

نرى ان العقدة B تحتوي على الرقم 8 والعقدة C تحتوي على الرقم 14 والعقدة D تحتوي على الرقم 7
من أين اتت هذه الارقام
لنحلل الشكل
قلنا أن أقل رقم بين العقدة A والعقدتين B و E هو 5
والمسافة التي بين العقدة E والعقدة B هي 3 كما في الشكل إذن وبالتالي تكون المسافة بين العقدة A وB هي 8 إذن أقصر مسار للوصول إلى العقدة B هي بالمرور على العقدة E ثم الوصول إلى العقدة B لأن المسافة بالمرور على العقدة E ومن ثم الوصول للعقدة B هي 8
أما من العقدة A إلى B مباشرة فهي 10
كذلك الأمر بالنسبة للعقدة C أي نضيف 5 على المسافة التي بين العقدة E و العقدة C فتصبح 14
وكذلك بالنسبة للعقدة D فتصبح 7
نضع جدول بين الأمر

من خلال الجدول نرى أن 7 هو أقل رقم الآت من العقدة E
الحين ننطلق من العقدة D
لأنه ومن خلال الجدول نرى ان العقدة D في أقل رقم من العقد الاخرى الذي هو الرقم 7
العقدة D تؤدي فقط إلى العقدة C
إذن تصبح العقدة C تساوي 7+6=13
نلاحظ ان العقدة D لا توصل للعقدة B إذن العقدة B تبقى تساوي 8
نلاحظ الصورة للحالة الجديدة

الجدول لتحليل الصورة

إذن نلاحظ في الجدول ان العقدة B تحتوي على أقل رقم الآت من العقدة E

ونلاجظ ان العقدة B تعطي للعقدة C إذن
نقوم بإظافة 8 على المسافة التي بين العقدة B و C فتصبح العقدة C تساوي 9
إذن خلاصة الامر للوصول إلى العقدة C من أقصر الطرق نسلك العقدة E ومن ثم العقدة B وأخيرا نصل إلى العقدة العقدة الهدف C
وللوصول إلى العقدة D من أقصر الطرق نسلك العقدة E ونصل إلى العقدة D

اترككم مع الصورة النهائية

والجدول التوضيحي

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

هذا كود بسيط بالسي ++ حول خوارزمية ديجيكسترا .