ما هي خوارزمية Dijkstra في شبكات الحاسوب

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

ما هي خوارزمية Dijkstra

خوارزمية “Dijkstra”: هي خوارزمية جشعة مشهورة جداً، ويتم استخدامه لحل مشكلة أقصر مسار بمصدر واحد، حيث يحسب أقصر مسار من عقدة مصدر معينة إلى جميع العقد المتبقية الأخرى في الرسم البياني.

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

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

• يبدأ بالعقدة المصدر ويجد بقية المسافات من العقدة المصدر.

• تحتفظ خوارزمية “Dijkstra” بتتبع المسافة المعروفة حالياً من عقدة المصدر إلى بقية العقد وتحديث هذه القيم ديناميكياً إذا تم العثور على مسار أقصر.

• يتم بعد ذلك وضع دلالة على العقدة على أنّها تمت زيارتها وإضافتها إلى المسار إذا كانت المسافة بينها وبين العقدة المصدر هي الأقصر.

• يستمر هذا حتى تتم إضافة جميع العقد إلى المسار.

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

• كما تحتاج إلى أوزان موجبة لأنّه يجب إضافتها إلى الحسابات لتحقيق الهدف، والأوزان السلبية تجعل الخوارزمية لا تعطي النتائج المرجوة.

مكونات خوارزمية Dijkstra

أولاً: المدخلات

• رسم بياني يمثل الشبكة.

• وعقدة المصدر “s”.

ثانياً: النواتج

أقصر شجرة مسار “spt []”، مع “s” كعقدة جذر.

ثالثاً: التهيئة

مجموعة مسافات [] من الحجم | V | (عدد العقد)، حيث dist [s] = 0 وdist [u] = ∞ (لانهائي)، وحيث تمثل “u” عقدة في الرسم البياني باستثناء s.

رابعاً: المصفوفة Q

• تحتوي على جميع العقد في الرسم البياني.

• عندما تكتمل الخوارزمية سيصبح “Q” فارغاً.

خامساً: مجموعة فارغة “S”

• ستتم إضافة العقد التي تمت زيارتها.

• عندما تكتمل الخوارزمية ستحتوي “S” على جميع العقد في الرسم البياني.

خطوات عمل خوارزمية Dijkstra

• عند التكرار وبينما Q ليس فارغاً

• يتم إزالة من “Q” والعقدة “u” التي لها أصغر مسافة [u] والتي ليست في “S”، وفي التشغيل الأول تتم إزالة “dist [s]”.

• أضف u إلى S، مع وضع علامة u على أنّه تمت زيارته.

• لكل عقدة v المجاورة لـ u، قم بتحديث dist [v]، إذا “(dist [u] + وزن الحافة u-v) <dist [v]”.

• ثم تحديث “dist [v] = dits [u] + وزن الحافة u-v”.

• تحتوي المصفوفة “dist []” على أقصر مسار من s إلى كل عقدة أخرى.

شروط استخدام خوارزمية Dijkstra

• تعمل خوارزمية “Dijkstra” فقط للرسوم البيانية المتصلة.

• تعمل خوارزمية “Dijkstra” فقط لتلك الرسوم البيانية التي لا تتضمن على أي حافة وزن سالب.

• لا تقوم خوارزمية “Dijkstra” الفعلية بإخراج أقصر المسارات.

• إنّه يوفر فقط قيمة أو تكلفة أقصر المسارات.

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

• تعمل خوارزمية “Dijkstra” مع الرسوم البيانية الموجهة وغير الموجهة.

أساسيات خوارزمية Dijkstra

تم تسمية خوارزمية “Dijkstra”، التي نُشرت في عام 1959م على اسم مكتشفها “Edsger Dijkstra” الذي كان عالم كمبيوتر هولندياً، حيث تهدف هذه الخوارزمية إلى إيجاد أقصر مسار في رسم بياني موجه أو غير موجه بأوزان حواف غير سلبية.

أولاً: الرسم البياني

الرسم البياني: هو بنية بيانات غير خطية مُعرَّفة على أنّها “G = (V ، E)”، حيث V عبارة عن مجموعة محدودة من الرؤوس وE هي مجموعة محدودة من الحواف بحيث تكون كل حافة عبارة عن خط أو قوس يربط بين أي رأسين.

ثانياً: الرسم البياني الموزون

الرسم البياني الموزون: هو نوع خاص من الرسم البياني يتم فيه تعيين قيمة عددية لكل حافة تسمى الوزن.

ثالثاً: الرسم البياني المتصل

يوجد مسار بين كل زوج من الرؤوس في هذا النوع من الرسم البياني.

رابعاً: الشجرة الممتدة للرسم البياني G

الشجرة الممتدة للرسم البياني “G”: هي عبارة عن رسم بياني فرعي “G’” بما في ذلك جميع رؤوس G المتصلة بأقل عدد من الحواف، وبالتالي بالنسبة للرسم البياني “G” الذي يحتوي على رؤوس “n”، فإنّ الشجرة الممتدة “G’” سيكون لها رؤوس n وحد أقصى n-1 من الحواف.

خامساً: عرض المشكلة

بالنظر إلى الرسم البياني الموزون “G” فإنّ الهدف هو إيجاد أقصر مسار من رأس مصدر محدد إلى جميع الرؤوس الموجوده في “G”.

سادساً: مجموعة من القمم V

مجموعة من القمم V: هي مجموعة من الحواف الموزونة “E” بحيث تشير “q وr” إلى حافة بين القمم “q وr” وتدل التكلفة “q وr” على وزنها.

ما هي خوارزمية Dijkstra

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

• تعمل هذه الخوارزمية لكل من الرسوم البيانية الموجهة وغير الموجهة.

• إنّه يعمل فقط للرسوم البيانية المتصلة.

• يجب ألّا يحتوي الرسم البياني على أوزان سالبة للحواف.

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

• يعتمد المنطق الرئيسي لهذه الخوارزمية على الصيغة التالية “dist [r] = min (dist [r]، dist [q] + cost [q] [r])”.

• تنص هذه الصيغة على أنّه سيتم تحديث رأس المسافة r والمجاور للرأس q، إذا وفقط إذا كانت قيمة “dist [q] + cost [q] [r] أقل من dist [r]”.

• التكلفة عبارة عن مصفوفة ثنائية الأبعاد، تمثل مصفوفة التكلفة المجاورة للرسم البياني.

• تستخدم هذه الصيغة كلا النهجين الجشع والديناميكي.

• يتم استخدام النهج الجشع لإيجاد قيمة المسافة الدنيا، بينما يتم استعمال النهج الديناميكي للجمع بين الحلول السابقة وتم حساب “dist [q]” بالفعل ويستخدم لحساب “dist [r]”.

ملاحظة:“dist” عبارة عن مصفوفة “1-D” والتي في كل خطوة تتعقب أقصر مسافة من رأس المصدر إلى جميع القمم الأخرى.

تطبيقات خوارزمية Dijkstra

• تستخدم أنظمة معلومات حركة المرور خوارزمية “Dijkstra” لتتبع الوجهات من موقع مصدر معين.

• يستخدم “OSPF” وهو بروتوكول توجيه قائم على الإنترنت ويستخدم خوارزمية “Dijkstra” للعثور على أفضل مسار من جهاز التوجيه المصدر إلى أجهزة التوجيه الأخرى في الشبكة.

• يتم استخدامه بواسطة الهاتف والشبكات الخلوية لإدارة التوجيه.

• يتم استخدامه أيضاً بواسطة نظام المعلومات الجغرافية “GIS“، مثل خرائط “Google” للعثور على أقصر طريق من النقطة A إلى النقطة B.

ملاحظة: “OSPF” هي اختصار لـ “Open Source Path First”.

ملاحظة:“GIS” هي اختصار لـ “Geographic Information System”.