خوارزمية دايجسترا لأقصر مسار: دليل شامل ومصور

أهلاً بك! إذا كنت تتطلع دائماً لتعلم وفهم خوارزمية دايجسترا (Dijkstra's Algorithm)، فهذا المقال هو دليلك الشامل. ستتعمق في كيفية عملها خلف الكواليس من خلال شرح رسومي مفصل خطوة بخطوة. ستتعلم في هذا المقال:

• مفاهيم الرسوم البيانية (Graph Concepts) الأساسية (مراجعة سريعة).
• ما هي استخدامات خوارزمية دايجسترا (Dijkstra's Algorithm).
• كيف تعمل الخوارزمية (Algorithm) بالتفصيل مع مثال عملي خطوة بخطوة.

لنبدأ رحلتنا المعرفية! ✨

مقدمة إلى الرسوم البيانية (Graphs)

دعنا نبدأ بمقدمة موجزة عن الرسوم البيانية.

مفاهيم أساسية في الرسوم البيانية

الرسوم البيانية (Graphs) هي هياكل بيانات تُستخدم لتمثيل ‘الروابط’ بين أزواج من العناصر. تُسمى هذه العناصر العُقد (nodes)، وهي تمثل كائنات أو أشخاص أو كيانات من العالم الحقيقي. أما الروابط بين العُقد فتُسمى الحواف (edges).

فيما يلي تمثيل رسومي لرسم بياني:

تُمثل العُقد (nodes) بدوائر ملونة، وتُمثل الحواف (edges) بخطوط تربط هذه الدوائر.

💡 نصيحة: تُعتبر العقدتان (nodes) متصلتين إذا كانت هناك حافة (edge) بينهما.

تطبيقات عملية للرسوم البيانية

تُطبق الرسوم البيانية (Graphs) بشكل مباشر في سيناريوهات العالم الحقيقي. على سبيل المثال، يمكننا استخدام الرسوم البيانية لنمذجة شبكة نقل حيث تمثل العُقد (nodes) المنشآت التي ترسل أو تستقبل المنتجات، وتمثل الحواف (edges) الطرق أو المسارات التي تربطها (انظر أدناه).

شبكة ممثلة باستخدام رسم بياني.

أنواع الرسوم البيانية

يمكن أن تكون الرسوم البيانية:

• غير موجهة (Undirected): إذا كان لكل زوج من العُقد المتصلة، يمكنك الانتقال من عقدة إلى أخرى في كلا الاتجاهين.
• موجهة (Directed): إذا كان لكل زوج من العُقد المتصلة، يمكنك الانتقال من عقدة إلى أخرى في اتجاه محدد فقط. نستخدم الأسهم بدلاً من الخطوط البسيطة لتمثيل الحواف الموجهة (directed edges).

💡 نصيحة: في هذا المقال، سنعمل مع الرسوم البيانية غير الموجهة (undirected graphs).

الرسوم البيانية الموزونة (Weighted Graphs)

الرسم البياني الموزون (weighted graph) هو رسم بياني تكون لحوافه ‘وزن’ (weight) أو ‘تكلفة’ (cost). يمكن أن يمثل وزن الحافة (edge) المسافة أو الوقت أو أي شيء ينمذج ‘الاتصال’ بين زوج العُقد (nodes) الذي يربطه. على سبيل المثال، في الرسم البياني الموزون أدناه، يمكنك رؤية رقم أزرق بجانب كل حافة. يُستخدم هذا الرقم لتمثيل وزن الحافة المقابلة.

💡 نصيحة: هذه الأوزان ضرورية لخوارزمية دايجسترا (Dijkstra's Algorithm). ستعرف السبب بعد قليل.

مقدمة إلى خوارزمية دايجسترا (Dijkstra’s Algorithm)

الآن بعد أن عرفت المفاهيم الأساسية للرسوم البيانية، دعنا نبدأ بالتعمق في هذه الخوارزمية المذهلة.

الغرض وحالات الاستخدام

باستخدام خوارزمية دايجسترا (Dijkstra's Algorithm)، يمكنك العثور على أقصر مسار بين العُقد (nodes) في رسم بياني (graph). على وجه الخصوص، يمكنك العثور على أقصر مسار من عقدة (تُسمى ‘العقدة المصدر’ – source node) إلى جميع العُقد الأخرى في الرسم البياني، مما ينتج عنه شجرة أقصر مسار (shortest-path tree). تُستخدم هذه الخوارزمية في أجهزة GPS للعثور على أقصر مسار بين الموقع الحالي والوجهة. ولها تطبيقات واسعة في الصناعة، خاصة في المجالات التي تتطلب نمذجة الشبكات.

لمحة تاريخية

ابتكر هذه الخوارزمية ونشرها الدكتور إدجر دبليو دايجسترا (Dr. Edsger W. Dijkstra)، عالم الحاسوب ومهندس البرمجيات الهولندي اللامع. في عام 1959، نشر مقالاً من 3 صفحات بعنوان “ملاحظة حول مشكلتين فيما يتعلق بالرسوم البيانية” (A note on two problems in connexion with graphs) حيث شرح خوارزميته الجديدة.

الدكتور إدجر دايجسترا في ETH Zurich عام 1994 (صورة بواسطة Andreas F. Borchert)

خلال مقابلة في عام 2001، كشف الدكتور دايجسترا كيف ولماذا صمم الخوارزمية:

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

— مقتبس من مقال إدجر دبليو دايجسترا من مقابلة مع إدجر دبليو دايجسترا.

⭐ أمر لا يُصدق، أليس كذلك؟ في 20 دقيقة فقط، صمم الدكتور دايجسترا واحدة من أشهر الخوارزميات في تاريخ علوم الحاسوب.

أساسيات خوارزمية دايجسترا

تبدأ خوارزمية دايجسترا (Dijkstra's Algorithm) بشكل أساسي من العقدة (node) التي تختارها (العقدة المصدر – source node) وتحلل الرسم البياني (graph) للعثور على أقصر مسار (shortest path) بين تلك العقدة وجميع العقد الأخرى في الرسم البياني. تحتفظ الخوارزمية بسجل لأقصر مسافة معروفة حالياً من كل عقدة إلى العقدة المصدر وتقوم بتحديث هذه القيم إذا وجدت مساراً أقصر.

بمجرد أن تعثر الخوارزمية على أقصر مسار بين العقدة المصدر وعقدة أخرى، يتم تمييز تلك العقدة على أنها ‘مزارة’ (visited) وتُضاف إلى المسار. تستمر العملية حتى يتم إضافة جميع العقد في الرسم البياني إلى المسار. بهذه الطريقة، نحصل على مسار يربط العقدة المصدر بجميع العقد الأخرى باتباع أقصر مسار ممكن للوصول إلى كل عقدة.

متطلبات الخوارزمية

يمكن لخوارزمية دايجسترا (Dijkstra's Algorithm) أن تعمل فقط مع الرسوم البيانية (graphs) التي تحتوي على أوزان إيجابية (positive weights). هذا لأنه، خلال العملية، يجب إضافة أوزان الحواف (edges) للعثور على أقصر مسار. إذا كان هناك وزن سلبي (negative weight) في الرسم البياني، فلن تعمل الخوارزمية بشكل صحيح. بمجرد تمييز عقدة (node) على أنها ‘مزارة’ (visited)، يتم اعتبار المسار الحالي لتلك العقدة هو أقصر مسار للوصول إليها. ويمكن للأوزان السلبية أن تغير هذا إذا كان من الممكن تقليل الوزن الكلي بعد حدوث هذه الخطوة.

مثال عملي على خوارزمية دايجسترا

الآن بعد أن عرفت المزيد عن هذه الخوارزمية، دعنا نرى كيف تعمل خلف الكواليس من خلال مثال خطوة بخطوة. لدينا هذا الرسم البياني:

ستقوم الخوارزمية بإنشاء أقصر مسار من العقدة 0 إلى جميع العقد الأخرى في الرسم البياني.

💡 نصيحة: بالنسبة لهذا الرسم البياني، سنفترض أن وزن الحواف (edges) يمثل المسافة بين عقدتين (nodes). سيكون لدينا أقصر مسار من العقدة 0 إلى العقدة 1، ومن العقدة 0 إلى العقدة 2، ومن العقدة 0 إلى العقدة 3، وهكذا لكل عقدة في الرسم البياني.

في البداية، لدينا هذه القائمة من المسافات (يرجى الاطلاع على القائمة أدناه):

• المسافة من العقدة المصدر (source node) إلى نفسها هي 0. في هذا المثال، ستكون العقدة المصدر هي العقدة 0، ولكن يمكن أن تكون أي عقدة تختارها.
• لم يتم تحديد المسافة من العقدة المصدر إلى جميع العقد الأخرى بعد، لذا نستخدم رمز اللانهاية (infinity symbol) لتمثيل ذلك في البداية.

لدينا أيضاً هذه القائمة (انظر أدناه) لتتبع العقد (nodes) التي لم تتم زيارتها بعد (العقد التي لم يتم تضمينها في المسار):

💡 نصيحة: تذكر أن الخوارزمية تكتمل بمجرد إضافة جميع العقد (nodes) إلى المسار (path).

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

الآن نحتاج إلى البدء في التحقق من المسافة من العقدة 0 إلى عقدها المجاورة (adjacent nodes). كما ترون، هذه هي العقدتان 1 و 2 (انظر الحواف الحمراء – red edges):

💡 نصيحة: هذا لا يعني أننا نضيف العقدتين المجاورتين على الفور إلى أقصر مسار (shortest path). قبل إضافة عقدة (node) إلى هذا المسار (path)، نحتاج إلى التحقق مما إذا كنا قد وجدنا أقصر مسار للوصول إليها. نحن ببساطة نقوم بعملية فحص أولية لرؤية الخيارات المتاحة.

نحتاج إلى تحديث المسافات من العقدة 0 إلى العقدة 1 والعقدة 2 بأوزان الحواف (weights of the edges) التي تربطها بالعقدة 0 (العقدة المصدر – source node). هذه الأوزان هي 2 و 6 على التوالي:

بعد تحديث مسافات العقد المجاورة (adjacent nodes)، نحتاج إلى:

• تحديد العقدة (node) الأقرب إلى العقدة المصدر (source node) بناءً على المسافات المعروفة حالياً.
• تمييزها على أنها مزارة (visited).
• إضافتها إلى المسار (path).

إذا فحصنا قائمة المسافات، يمكننا أن نرى أن العقدة 1 لديها أقصر مسافة إلى العقدة المصدر (مسافة 2)، لذلك نضيفها إلى المسار. في الرسم التخطيطي، يمكننا تمثيل ذلك بحافة حمراء (red edge):

نقوم بتمييزها بمربع أحمر في القائمة لتمثيل أنها ‘زُورت’ (visited) وأننا وجدنا أقصر مسار (shortest path) للوصول إلى هذه العقدة:

نقوم بشطبها من قائمة العقد غير المزارة:

الآن نحتاج إلى تحليل العقد المجاورة (adjacent nodes) الجديدة للعثور على أقصر مسار للوصول إليها. سنقوم بتحليل العقد المجاورة للعقد التي هي بالفعل جزء من أقصر مسار (المسار المميز بالحواف الحمراء – red edges). العقدة 3 والعقدة 2 كلاهما مجاورتان لعقد موجودة بالفعل في المسار لأنهما متصلتان مباشرة بالعقدة 1 والعقدة 0 على التوالي، كما ترون أدناه. هذه هي العقد التي سنقوم بتحليلها في الخطوة التالية.

بما أن لدينا بالفعل المسافة من العقدة المصدر (source node) إلى العقدة 2 مكتوبة في قائمتنا، لا نحتاج إلى تحديث المسافة هذه المرة. نحتاج فقط إلى تحديث المسافة من العقدة المصدر إلى العقدة المجاورة الجديدة (العقدة 3):

هذه المسافة هي 7. دعنا نرى لماذا. للعثور على المسافة من العقدة المصدر (source node) إلى عقدة أخرى (في هذه الحالة، العقدة 3)، نضيف أوزان جميع الحواف (weights of all the edges) التي تشكل أقصر مسار (shortest path) للوصول إلى تلك العقدة:

• للعقدة 3: المسافة الإجمالية هي 7 لأننا نضيف أوزان الحواف التي تشكل المسار 0 -> 1 -> 3 (2 للحافة 0 -> 1 و 5 للحافة 1 -> 3).

نضيفها إلى المسار (path) بيانياً بحد أحمر حول العقدة وحافة حمراء (red edge):

نقوم أيضاً بتمييزها على أنها مزارة (visited) بإضافة مربع أحمر صغير في قائمة المسافات وشطبها من قائمة العقد غير المزارة:

الآن نحتاج إلى تكرار العملية للعثور على أقصر مسار (shortest path) من العقدة المصدر (source node) إلى العقدة المجاورة (adjacent node) الجديدة، وهي العقدة 3. يمكنك أن ترى أن لدينا مسارين محتملين 0 -> 1 -> 3 أو 0 -> 2 -> 3. دعنا نرى كيف يمكننا تحديد أيهما أقصر مسار.

العقدة 3 لديها بالفعل مسافة في القائمة تم تسجيلها مسبقاً (7، انظر القائمة أدناه). كانت هذه المسافة نتيجة خطوة سابقة، حيث أضفنا الأوزان 5 و 2 للحافتين اللتين احتجنا لعبورهما لاتباع المسار 0 -> 1 -> 3. ولكن الآن لدينا بديل آخر. إذا اخترنا اتباع المسار 0 -> 2 -> 3، فسنحتاج إلى اتباع حافتين 0 -> 2 و 2 -> 3 بأوزان 6 و 8 على التوالي، مما يمثل مسافة إجمالية قدرها 14.

الآن نكرر العملية مرة أخرى. نحتاج إلى التحقق من العقد المجاورة (adjacent nodes) الجديدة التي لم نزرها بعد. هذه المرة، هذه العقد هي العقدة 4 والعقدة 5 لأنهما مجاورتان للعقدة 3.

نقوم بتحديث مسافات هذه العقد إلى العقدة المصدر (source node)، محاولين دائماً العثور على مسار أقصر (shorter path)، إذا أمكن:

• للعقدة 4: المسافة هي 17 من المسار 0 -> 1 -> 3 -> 4.
• للعقدة 5: المسافة هي 22 من المسار 0 -> 1 -> 3 -> 5.

💡 نصيحة: لاحظ أنه يمكننا فقط التفكير في تمديد أقصر مسار (shortest path) (المميز باللون الأحمر). لا يمكننا النظر في المسارات التي ستأخذنا عبر حواف (edges) لم تتم إضافتها إلى أقصر مسار (على سبيل المثال، لا يمكننا تشكيل مسار يمر عبر الحافة 2 -> 3).

نحتاج إلى اختيار أي عقدة (node) غير مزارة (unvisited) ستُعلم على أنها مزارة (visited) الآن. في هذه الحالة، إنها العقدة 4 لأنها تحتوي على أقصر مسافة (shortest distance) في قائمة المسافات. نضيفها بيانياً في الرسم التخطيطي:

نقوم أيضاً بتمييزها على أنها ‘مزارة’ (visited) بإضافة مربع أحمر صغير في القائمة:

ونشطبها من قائمة العقد غير المزارة:

ونكرر العملية مرة أخرى. نتحقق من العقد المجاورة (adjacent nodes): العقدة 5 والعقدة 6. نحتاج إلى تحليل كل مسار ممكن يمكننا اتباعه للوصول إليهما من العقد التي تم تمييزها بالفعل على أنها مزارة (visited) وإضافتها إلى المسار (path).

• للعقدة 5:
  • الخيار الأول هو اتباع المسار 0 -> 1 -> 3 -> 5، والذي تبلغ مسافته 22 من العقدة المصدر (2 + 5 + 15). تم تسجيل هذه المسافة بالفعل في قائمة المسافات في خطوة سابقة.
  • الخيار الثاني هو اتباع المسار 0 -> 1 -> 3 -> 4 -> 5، والذي تبلغ مسافته 23 من العقدة المصدر (2 + 5 + 10 + 6).

  من الواضح أن المسار الأول أقصر، لذلك نختاره للعقدة 5.

• للعقدة 6:
  • المسار المتاح هو 0 -> 1 -> 3 -> 4 -> 6، والذي تبلغ مسافته 19 من العقدة المصدر (2 + 5 + 10 + 2).

نقوم بتمييز العقدة (node) ذات أقصر مسافة (shortest distance) (المعروفة حالياً) على أنها مزارة (visited). في هذه الحالة، العقدة 6.

ونشطبها من قائمة العقد غير المزارة:

الآن لدينا هذا المسار (path) (المميز باللون الأحمر):

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

• الخيار 1: 0 -> 1 -> 3 -> 5 بمسافة 22 (2 + 5 + 15).
• الخيار 2: 0 -> 1 -> 3 -> 4 -> 5 بمسافة 23 (2 + 5 + 10 + 6).
• الخيار 3: 0 -> 1 -> 3 -> 4 -> 6 -> 5 بمسافة 25 (2 + 5 + 10 + 2 + 6).

نختار أقصر مسار (shortest path): 0 -> 1 -> 3 -> 5 بمسافة 22.

وهكذا! حصلنا على النتيجة النهائية مع أقصر مسار (shortest path) من العقدة 0 إلى كل عقدة في الرسم البياني (graph).

في الرسم التخطيطي، تحدد الخطوط الحمراء (red lines) الحواف (edges) التي تنتمي إلى أقصر مسار (shortest path). تحتاج إلى اتباع هذه الحواف لاتباع أقصر مسار للوصول إلى عقدة (node) معينة في الرسم البياني (graph) بدءاً من العقدة 0. على سبيل المثال، إذا كنت ترغب في الوصول إلى العقدة 6 بدءاً من العقدة 0، فما عليك سوى اتباع الحواف الحمراء وستتبع أقصر مسار 0 -> 1 -> 3 -> 4 -> 6 تلقائياً.

ملخص خوارزمية دايجسترا

تُستخدم الرسوم البيانية (Graphs) لنمذجة الروابط بين الكائنات أو الأشخاص أو الكيانات. ولها عنصران رئيسيان: العقد (nodes) والحواف (edges). تمثل العقد الكائنات، وتمثل الحواف الروابط بين هذه الكائنات.

تجد خوارزمية دايجسترا (Dijkstra's Algorithm) أقصر مسار (shortest path) بين عقدة معينة (تُسمى ‘العقدة المصدر’ – source node) وجميع العقد الأخرى في الرسم البياني (graph). تستخدم هذه الخوارزمية أوزان الحواف (weights of the edges) للعثور على المسار الذي يقلل المسافة الإجمالية (الوزن – weight) بين العقدة المصدر وجميع العقد الأخرى.

آمل حقاً أن يكون المقال قد نال إعجابك ووجدته مفيداً. الآن أنت تعرف كيف تعمل خوارزمية دايجسترا (Dijkstra's Algorithm) خلف الكواليس.

الخلاصة التقنية

تمثل خوارزمية دايجسترا (Dijkstra's Algorithm) حجر الزاوية في مجال خوارزميات الرسوم البيانية (graph algorithms)، حيث توفر حلاً فعالاً وموثوقاً لإيجاد أقصر المسارات في الرسوم البيانية الموزونة ذات الأوزان الإيجابية. تكمن قوتها في منهجيتها التكرارية التي تضمن العثور على المسار الأمثل تدريجياً، مما يجعلها لا غنى عنها في تطبيقات مثل توجيه الشبكات، أنظمة الملاحة (GPS)، وتخطيط المسارات اللوجستية. إن فهم آلياتها الأساسية، كما تم توضيحه في هذا المقال، يفتح آفاقاً واسعة للمطورين والمهندسين لمعالجة تحديات التحسين في أنظمة العالم الحقيقي.