بسمِ اللهِ الرحمنِ الرحيم

نستأنف اليوم حديثنا عن المِبيان (Graph) وما يتصل به من طرائق السير في شبكاته ومسالكه، فنعرّج على خوارزميةٍ شاع ذكرُها في الآفاق حتى صارت عند أهل الصنعة كالعُملة الجارية، يرجعون إليها كلما ضاقت المسالك وتشعّبت الطرق.

والعجب أيها المعبسس أنّ واضعها لم يكن يتقصّد يومئذٍ وضعَها، ولا كان يتهيّأ لها بما يتهيّأ العلماءُ عادةً من تجريد الفكر ورصّ الأوراق وتدقيق المعاني، ولكنها خطرت في خاطرٍ صافٍ، وبيئةٍ لا يظنّ العوامّ أنها تُنبت علمًا ولا تُثمر فهمًا.

نُحدِّثك في هذا المقال عن خوارزمية ديكسترا (Dijkstra Algorithm) للبحث عن أقصر طريق؛ وهي وإن كانت أختًا لخوارزمية البحث المُتَّسِع Breadth-First Search (BFS) وتشترك معها في الأصل، فإنها تمتاز عنها بميزةٍ ظاهرة، وتغايرها في جوهرٍ دقيق ستراه اليوم.

🔗 إن لم تقرأ مقالنا عن خوارزمية البحث المتسع فاذهب لقراءته مشكورًا.

https://bassye.org/grokking_algorithms_6_4/

وقبل الشروع بها يُستَحسن بي أن أقص لك طرفًا من سيرة واضع (مخترع) الخورازمية أيدسكر فيبِ دايكسترا Edsger Wybe Dijkstra (وهي باسمه)، ثم أتبعها بقصة طريفة عن نشأة الخوارزمية، ثم نلج إلى الخوارزمية بعون الله.

---

🧠 أيدسكر فيبِ دايكسترا

Edsger Wybe Dijkstra

أيدِسكَر دايكسترا عالم رياضيات وحوسبة هولندي النشأة، من أوائل من أسهموا في وضع أسس علم الحوسبة الحديث، وقد وُلد في روتردام عام ١٩٣٠م، ونشأ في بيت علم ومعرفة، فترعرع على حب الحساب والمنطق، وأظهر في شبابه ميلًا إلى التفكير المنظم والتحليل الدقيق.

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

وقد كان يختلف عن سائر الباحثين في زمانه في ميله إلى:

• 🧩 الاقتصاد في الفكر

• ✨ وضوح البرهان

• 🚫 رفض التعقيد الذي لا داعي له

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

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

• 🌐 الشبكات

• 💻 البرمجة

يُستفاد منها في جميع:

• 📡 نظم الاتصالات

• 🗺️ نظم الملاحة والطرق

كما كانت له إسهامات بارزة في:

• مشكلات التزامن

• طرق تنظيم البرامج

• الكتابات النقدية في فلسفة البرمجة

ومن أشهر مقالاته:

⚠️ مقاله الشهير الذي هاجم فيه استعمال الأمر Goto
وما أثارته من ضجة في عالم البرمجة حينها، لما حملته من فلسفة واضحة في بناء البرامج:
البرمجة ليست مجرد تنفيذ، بل فن يعتمد على النظام والوضوح والدقة

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

• برامج الحواسيب

• أنظمة الاتصالات

• شبكات النقل

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

• 🧠 يفضل الحلول الواضحة على المعقدة

• 🎯 الفكرة الصريحة على المزخرفة

مما جعله قدوة للباحثين، ونموذجًا يُحتذى به في عالم البرمجة.

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

---

☕ قصة وضع خوارزمية ديكسترا

خذه الخوارزمية لم تخطر لذهن أيدسكر فيبِ دايكسترا بعد كد النظر وإتعاب الفكر، بل جاءت إلى العالم كوميض خاطف في لحظة هدوء وعفوية، لم يتكلفها!

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

وهناك، في تلك اللحظة الهادئة وبين صخب المارّة وهدير المدينة، جاءته الفكرة:

🧠  كيف يُمكن أن أجد أقصر طريق بين مدينة وأخرى، بين روتردام وجرونينجن، أو في أي شبكة من المدن، بحيث يُختصر الجهد والوقت؟

ولم يمضِ إلا نحو عشرين دقيقة حتى تشكلت الخوارزمية في ذهنه، كاملة متكاملة، بلا قلمٍ ولا ورقة.

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

بل لأننا نريد أن ننهي اليوم بسلام.

---

🚶‍♂️🛍️ لفته مني…. 😈 “خوارزمية الهروب”

 هذا ما يروى عنه ولكن لم تكن القهوة وحدها هي المحفّز.
فأحيانًا، نكد اللحظات الطويلة، وكثرة الطلبات التي لا تنتهي، والتنقّل بين متجر وآخر، تدفع العقل البشري إلى أقصى طاقاته الدفاعية! 😅

حينها لا يبحث الذهن عن أقصر طريق بين مدينتين فحسب،
بل عن أقصر طريق للنجاة…
طريق يعيدك سريعًا إلى هدوءك،
إلى أريكتك،
إلى يد التحكم 🎮،
أو إلى حلقة جديدة من ون بيس 🏴‍☠️.

وهكذا، بدل أن يضيع في دوّامة التبرّم،
حوّل ديكسترا الضغط اللحظي إلى فكرة خالدة،
وأثبت — من حيث لا يدري — أن بعض أعظم الخوارزميات في التاريخ
ربما وُلدت فقط
لأن أحدهم أراد أن يُنهي يومه… براحة بال…

---

📄 نشر الخوارزمية وانتشارها

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

ولدهشة دايكسترا صارت هذه اللمحة العابرة = أساسًا في علم الحوسبة، تُدرّس في الجامعات، وتُطَبَّق في برمجيات الحواسيب، وفي شبكات النقل والاتصالات، لتقود الباحثين والمهندسين نحو فهم أفضل للطريقة الأمثل في أي شبكة أو مِبيان.

---

🌱 العبقرية بين الصدفة والضرورة

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

هناك، حيث يلتقي الفكر العميق بالإلهام العفوي، تنبثق بصائر تغيّر مجرى العلوم كلها.

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

---

⚠️ قُصور خوارزمية البحث المتسع

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

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

📌 انظر للصورة وسترى أسرع طريق:

 

أسرع طريق استغرق ٢٤ دقيقة
(١٠ + ٥ + ٥ + ٤ = ٢٤)

أما خوارزمية البحث المتسع إن طبقناها فإنها ستبحث عن أقصر طريق، الذي هو أقل خطوات للوصول إلى الوجهة:

(٤ + ٢١ + ٤ = ٢٩ دقيقة)

فليس هو الأسرع (زمنيًا) بل الأقصر أو الأقل في الخطوات، لأننا نريد الوصول في وقت أقل لا أن نسير خطوات أقل!

ولأنها تعجز عن ذلك = أتت خوارزمية ديكسترا التي تخبرنا عن أسرع طريق، لأنها تقيم للزمن وزنًا.

نعم كما قرأت، فأنت تخبرها أن تقيم للشيء وزنًا، وهي في مثالنا الزمن، أما خوارزمية البحث المتسع فلا تفعل ذلك، إنما تخبرك بأقصر طريق ولا تعبأ إن كان الأبطأ، فكل همها = أقل الخطوات مع إغفال أي أمر آخر.

❓ لِمَ أخفقت خوارزمية البحث المتسع؟

أليست تعطينا الطريق الأقصر؟

🧩 المِبيان الموزون (Weighted Graph)

سبب إخفاق خوارزمية البحث المتسع أنها لا تُطبَّق على المِبيان الموزون (Weighted Graph)، وقد تقدم بنا الكلام في أول مقالة في الفصل السادس وتحدثنا عن أنواع المِبيان، وذكرنا المِبيان الموزون.

فالمِبيان نوعان، مبيان عادي ومِبيان موزون.

⚖️ ما هو المِبيان الموزون؟

المِبيان الموزون هو أن نعطي للشيء وزنًا، أي قيمة، وفي مثالنا السابق كان الزمن، لأننا نريد الأسرع، والسرعة تقاس بالمسافة المقطوعة في زمن.

📌 انظر المِبيان الموزون:

الرقم الذي عند كل وصلة edge هو زمن المسير لكل عقدة، فالمسير من مكان البداية إلى العقدة التالية يكون في ست دقائق، وهكذا كل مسلك في الصورة له زمن.

🚶‍♂️ لماذا BFS لا تكفي؟

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

قد يكون الطريق أقصر خطواتٍ لكنه في الزمن بطيء، كأن يكون الطريق الفلاني مزدحمًا، فالأقصر لا يعني الأسرع.

🛤️ الحل: خوارزمية ديكسترا

الخوارزمية التي تُطبَّق على المِبيان الموزون هي خوارزمية ديكسترا، ولها نهج يميزها عن أختها القاصرة عنها، ودونك تفصيله:

🧭 نهج خوارزمية ديكسترا

نهج خوارزمية ديكسترا المُتّبَع
(على سبيل الإجمال ثم يتلوها التفصيل والمثال):

1️⃣ نبحث أوّلًا عن أقرب عُقدة يمكن الوصول إليها بأقل زمن.

2️⃣ ثم نراجع الطرق المؤدية إلى جيرانها، فإن وجدنا طريقًا أقرب ممّا سُجِّل، أثبتناه مكانه
(إن لم تفهم فلا تبتئس، شرحها آتٍ).

3️⃣ نكرر ما سبق لكل عُقدة في المِبيان حتى تتّضح كلفة الوصول إلى كلّ موضع.

4️⃣ احسب زمن الطريق النهائي.

---

🔍 تفصيل كل خطوة في نهج الخوارزمية

---

🥇 الخطوة الأولى

نبحث أوّلًا عن أقرب عُقدة يمكن الوصول إليها بأقل زمن.

نقف في البداية، ثم من هذا الموضع يتفرّع أمامك طريقان:

• 🛤️ طريقٌ يؤدي إلى الموضع أ

• 🛤️ طريقٌ آخر يؤدي إلى الموضع ب

ونسأل: كم يستغرق الوصول إلى كلٍّ منهما؟

يستغرق ست دقائق إلى المكان أ،
ودقيقتين إلى المكان ب.

أما سائر العُقَد فأنت لا تعرفها الآن، ولأن زمنها غير معلوم، نضع لكلٍّ منها قيمة كبيرة جدًّا هي المتناهية infinity (ولا تقل لا نهائية).

وسبب وضعها أننا لا نعلم أين النهاية، فوضعنا لها قيمة اسمها الرياضي المتناهية، لأنها تتناهى إلى غاية غير معلومة!

إذن أقرب عقدة نصل إليها هي العقدة ب، لأنها لا تبعد إلا دقيقتين، وهو أقل زمن ممكن.

سنأخذ كل عقدة ونضعها في جدول، ومعها الزمن:

🎯 الوجهة (Destination)

(الوجهة) هي نقطة النهاية التي نود الوصول إليها بالخوارزمية بأسرع طريق.

انظر إذا طبقنا خوارزمية البحث المتسع، ستكون النتيجة (سبع دقائق):

🔁 الخطوة الثانية: عدل الكلفة لجيران هذه العقدة

احسب مقدار الوقت اللازم للوصول إلى كلِّ جار من جيران العقدة ب، وهي العقدة التي اخترناها في الخطوة الأولى.
ثم انظر في كلِّ طريقٍ يتفرّع من ب، ودوّن ما يحتاجه اجتياز هذا الطريق من وقت، لتعرف أيَّ الطرق أقصر زمناً وأقلَّ كلفة.

بمعنى أننا سنمسك العقدة (ب) ونرى كم الوقت المستغرق للوصول إلى كل جار من جيران هذه العقدة.

---

🔗 جيران العقدة (ب)

للعقدة جارين هما:

• (أ)
  ⏱️ والوقت للوصول إليه: ٣ دقائق

• (النهاية)
  ⏱️ الوقت للوصول إاليها: خمس دقائق

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

• ⏱️ خمس دقائق للوصول إلى (أ)

• ⏱️ وسبع دقائق للوصول إلى (النهاية)

---

الآن ما الذي قصدناه بقولنا: تعديل التكلفة لجيران هذه العقدة؟

الجدول السابق كان فيه العُقَد مع الوقت المُستَغرق، وقد كان:
ست دقائق إلى (أ)، أما (النهاية) فكانت قيمتها متناهية.

أما في الخطوة الثانية عثرنا على:

1. 🛣️ طريق جديد إلى العُقدة (أ) يستغرق خمس دقائق،

 

2. 🏁 عرفنا أن الوقت المُستَغرق إلى (النهاية) كان سبع دقائق.

أما في الجدول فكانت (النهاية) قيمتها متناهية، لكننا سنعدلها في الجدول لتكون: ٧ دقائق،
أما العُقدة (أ) سنعدلها من ٦ دقائق إلى ٥ دقائق.

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

---

🔁 الخطوة الثالثة: نكرر ما سبق لكل عُقدة في المِبيان حتى تتّضح كلفة الوصول إلى كلّ موضع

🔄 تكرار الخطوة الأولى:

بما أننا قد فرغنا من العُقدة (ب) ولم يَبق لنا في المِبيان إلا العُقدة (أ) لم نجرب عليها، فإننا سنجرب عليها!

---

🔍 فحص جيران العقدة (أ)

سنأخذها ونرى جيرانها،
وليس معها إلا جار واحد، هو الخط المشير إلى مكان (النهاية) ويستغرق دقيقة واحدة.

---

ثم نضيف الرقم خمسة للواحد!

لأنك سلكت الطريق:

• من البداية إلى (ب) في دقيقتين،

• ثم من (ب) إلى (أ) في ثلاث دقائق → (٣ + ٢ = ٥)،

• ثم من (أ) إلى النهاية في دقيقة → (٥ + ١ = ٦)،

فالنتيجة ستة!

---

✏️ تكرار الخطوة الثانية:

نعدل الآن الكلفة لجيران العُقدة،
وقد قلنا إنه جار للعُقدة (النهاية)،
وقد كانت في الجدول قيمتها ٧، لكنها الآن صارت ستة،
وبما أنها أقل من القيمة التي في الجدول فإننا سنعدلها لتصير ستة:

وها قد انتهينا من تطبيق الخوارزمية على كل عُقدة في المِبيان، ولم يتبقَ لنا أي عُقدة للتطبيق عليها،
إذن نتوقف ونرى قيمة (النهاية)، وهي ستة، وهذه النتيجة النهائية!

⏱️ عرفنا أقصر طريق بخوارزمية ديكسترا وكان في ست دقائق!

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

🔁 الحَلَقة في المِبيان

تحدث في الكتاب عن الحَلَقة في المِبيان،
ومعناها أن تبدأ من نفس المكان وتعود إليه،
فأنت في حَلَقة، أي دائرة،
تبدأ من مكان وتنتهي إليه،
فمكان الانطلاق هو مكان التوقف!

ثم ذكر المِبيان المُطلق والمِبيان الموجَّه
(وقد شرحتهما لك في المقال السابق فراجعه).

بما أن كل عقدة تتصل بأختها،
وأختها تتصل بها،
فإنها تنشأ حَلَقة بينهما!
انظر:

❌ خطأ شائع

ثم قال وهنا أخطأ الكاتب:
خوارزمية ديكسترا لا تعمل إلا على المِبيان الموجَّه الخالي من الحلقات (DAG).

وهذا الكلام خطأ!

فخوارزمية ديكسترا لا تشترط أن يكون المِبيان موجّهًا،
ولا أن يكون خاليًا من الحلقات،
بل تعمل عملًا سليمًا على المِبيان الموجَّه والمُطلق،
سواء كان فيه حلقات أم لم يكن.

والحالة الوحيدة التي تُخفِق فيها خوارزمية ديكتسرا هي:

⚠️ أن يكون الوزن بالسالب

على كل وزن في المِبيان أن لا يكون سالبًا،
وإنما موجب القيمة.

فهذه الحالة الوحيدة التي تُخفِق فيها خوارزمية ديكسترا،
أما ربطها بالمِبيان الموجَّه الخالي من الحلقات (DAG) فـ خطأ.

---

لهذا يجب التنبيه إلى أن الخلل ليس في وجود حلقة،
بل في وجود وزنٍ سالب؛
فهو وحده ما يُفسد نتائج الخوارزمية.

وفي هذه الحالة
(حالة الوزن السالب)
نستعمل خوارزمية أخرى اسمها:

🔁 خوارزمية بيلمان–فورد Bellman–Ford

وهي مصممة للعمل على المِبيان الذي فيه وزن سالب.

---

🧩 المثال المكتمل

المثال السابق كان سهلًا، لأن العُقد في المِبيان كانت قليلة (عقدتان) ويَسهل تتبعها،
لكن عندما يتعقد المِبيان سترى قصور المثال الأول وأنه لا يفهمك الخوارزمية بحق فهمها
إلا بمثال لمِبيان معقد مثل هذا:

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

كما في المثال الأول، نبدأ بوضع كل العُقَد في جدول لمتابعة أقل تكلفة للوصول إليها
(لكل عُقدة في المِبيان).

لكن هذه المرة علينا إضافة عمود جديد في الجدول نسميه:

• العقدة السابقة

• أو العقدة الأب

• Parent / Previous Node

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

مثلا:
إذا وصلنا إلى العقدة (ب) عبر العقدة (أ) بأقل تكلفة،
فإننا نسجل في خانة “العقدة الأب”: (أ)،
لتخبرنا أننا أتينا إلى (ب) عبر العُقدة (أ).

هذه الإضافة مهمة حتى تتم الخوارزمية.

وضعنا قيمة (أ): صِفر،
لأننا سنبدأ من هنا، وما زلنا لا نعرف شيئًا،
والذهاب من هذه النقطة وهي (أ) إلى نفسها يساوي الصفر،
لهذا وضعنا صِفرًا.

وكما ترى العمود الثالث خالٍ،
لأننا ما بدأنا أي شيء.

ثم سنضيف لائحتين:

• 🟢 الأولى فيها العُقَد المُزارة،
  حتى لا نزور العُقَدة نفسها مرتين.

• 🔵 واللائحة الثانية للعُقَد غير المُزارة،
  حتى نزورها كلها،
  لأنه كما تقدم، علينا تطبيق الخوارزمية على كل عُقدة في المِبيان.

تجهزنا الآن لتطبيق الخوارزمية،
فهيا بنا!

🔁 لأذكرك بالخطوات الأربع

1. 🔍 نبحث أوّلًا عن أقرب عُقدة يمكن الوصول إليها بأقل زمن.

2. 🔄 ثم نراجع الطرق المؤدية إلى جيرانها، فإن وجدنا طريقًا أقرب ممّا سُجِّل، أثبتناه مكانه.

3. 🔁 نكرر ما سبق لكل عُقدة في المِبيان حتى تتّضح كلفة الوصول إلى كلّ موضع.

4. ⏱️ احسب زمن الطريق النهائي.

---

▶️ بدء التنفيذ

نبدأ من مكان البداية وهو العُقدة (أ)،
التي لها جارين هما: (ب) و**(جـ)**،

• قيمة الأولى: ٢

• وقيمة الثانية: ٨

انظر للجدول في الصورة،
قيمة كل من (ب) و**(جـ)** هي المتناهية ∞،
وقبل قليل عرفنا قيمة كل واحدة، إذن:

1. ✏️ سنُعدل القيمة في الجدول

2. 📌 نُزيل العُقدة (أ) من لائحة العُقد غير المُزارة
   ونضعها في لائحة العُقد المُزارة

العُقدة السوداء: عُقدة مُزارة قد فُرِغَ منها.

الآن نأخذ أقرب عقدة وهي الأقل كلفة (كما تقول الخطوة الأولى)، وهي العُقدة: (ب)، لأن قيمتها ٢ وهي أقل من ٨.

نبدأ من هذه العُقدة (ب) ونزور جيرانها وهما: العُقدة (د) والعُقدة (جـ):

ثم علينا إضافة ٢، وهي تكلفة العُقدة (ب)، إلى قيمة كلٍّ من العُقدة (د) والعُقدة (جـ)، أضفناها لأنها تمثل الطريق من بدايته، فأنت أتيت من العُقدة (أ) إلى العُقدة (ب) وكلفة الطريق ٢.

نتيجة الإضافة إلى العُقدة (د) = ٨
ونتيجة الإضافة إلى العُقدة (جـ) = ٧

بعد إضافة القيمة سنقارن القيم الجديدة (٨ و٧) بما كان معنا على الجدول، وقد كانت قيمة العُقدة (د) تساوي المتناهية ∞،والعُقدة (جـ) كانت ٨، والنتيجة الحالية هي: ٧.

والسبعة أقل من الثمانية، والخطوة الثانية تقول: (ثم نراجع الطرق المؤدية إلى جيرانها، فإن وجدنا طريقًا أقرب ممّا سُجِّل، أثبتناه مكانه)، وقد عثرنا على طريق أقصر من الطريق القديم الذي كان ثمانية، لهذا وجب حذفه وكتابة القيمة الجديدة لأنها أقصر!

كما ترى:
١. عدلنا قيمة العُقدة (د) والعُقدة (جـ)، الأولى من المتناهية إلى ٨، والثانية من ٨ إلى سبعة
٢. عدلنا عمود (العُقدة الأب) لكُلٍّ من العُقدة (د) والعُقدة (جـ) وجعلناها (ب)، لأننا أتينا منها إليهما.
٣. ثم أضفنا العُقدة (ب) إلى لائحة العُقد المُزارة، وهكذا لن نزورها مرة ثانية، وقد جعلت لونها بالأسود إشارة على أننا قد فرغنا منها.

الآن نطبق الخطوة الأولى مرة ثانية: (نبحث أوّلًا عن أقرب عُقدة يمكن الوصول إليها بأقل زمن “تكلفة”)، أي سنبحث عن الأقل تكلفة من بين العُقد التي هي جيران للعُقدة (ب): العُقدة (د) والعُقدة (جـ)، وهي العُقدة (جـ):

سنضيف القيمة ٧، وهي قيمة العُقدة (جـ)، المستخرجة من الطريق المسلوك من مكان البداية: من (أ) إلى (ب) = ٢، ومن (ب) إلى (جـ) = ٥، و٥+٢ = ٧

سنضيف القيمة ٧ إلى العُقدة (د) والعُقدة (هـ):
العُقدة (د) = ٣ + ٧ = ١٠
العُقدة (هـ) = ٢ + ٧ = ٩

سنأخذ هذه القيم ونضيفها إلى الجدول، ونلاحظ أول شيء أن كلفة العُقدة (د) تساوي ١٠، وهي أكبر من كلفتها على الجدول، لهذا لن نغيرها، سنغيرها إذا كان أقل، أما إذا كانت أكثر فلن نفعل!
أما العُقدة (هـ) سنغيرها من المتناهية ∞ إلى ٩، وثم نعدل عمود (العُقدة الأب) لها، أما العُقدة (د) ستبقى كما هي بلا تغيير، فلم نجد شيئًا نغيره لها:

كما ترى:
١. عدلنا كلفة العُقدة (هـ) من المتناهية إلى ٩
٢. عدلنا عمود (العُقدة الأب)للعُقدة (هـ) وجعلناها (جـ)، لأننا أتينا منها إليها.
٣. ثم أضفنا العُقدة (جـ) إلى لائحة العُقد المُزارة، وهكذا لن نزورها مرة ثانية، وقد جعلت لونها بالأسود إشارة على أننا قد فرغنا منها.

بعد تعديل الجدول = نرى أي العُقد من (د) و(هـ) هي الأقل كلفة ونأخذها لنطبق عليها ما طبقناها على أخواتها:
العُقدة (د) = ٨
العُقدة (هـ) = ٩
إذن سنأخذ العُقدة (د)، ونضيف إلى جيرانها القيمة ٨:

إضافة القيمة ٨ إلى كل عُقدة:
العُقدة (و) = ٩ + ٨ = ١٧
العُقدة (هـ) = ١ + ٨ = ٩

كلفة العُقدة (هـ) ما زالت هي القديمة، فلن نعدل في الجدول شيئًا
أما كلفة العُقدة (و) فقد كانت المتناهية ∞ أما الكلفة الجديدة فهي ١٧، وهي أقل من المتناهية، لهذا سنعدل كلفتها وسنعدل عمود (العُقدة الأب)، ثم نضيف العُقدة (د) إلى لائحة العُقد المُزارة:

الآن نأخذ أقل العُقد كلفة، العُقد المجاورة للعُقدة (د) وهما: العُقدة (و) وكلفتها ١٧، والعُقدة (هـ) وكلفتها ٩، والتسعة أصغر إذن سنأخذها ونطبق عليها ما سبق!

سنضيف قيمة ٩، وهي قيمة العُقدة (هـ) التي توضع المسار الذي سرنا فيه إليها، ثم بعد الإضافة سنرى هل نعدل الجدول أم لا؟
سنعدل الجدول لأن ٩ + ٣ = ١٢، والتكلفة القديمة للعُقدة (و) كانت ١٧، والنتيجة الجديدة هي ١٢، لذا سنعدلها إلى ١٢، ونعد عمود (العُقدة الأب) ليكون (هـ).
ثم سننقل العُقدة (هـ) إلى لائحة العُقد المُزارة:

تبقى معنا عُقدة واحدة هي العُقدة (و)، وهي نفس العُقدة التي نريد الوصول لها، إنها الوجهة. ولأنها لا تملك أي جيران فإننا سنتوقف هنا ونضيفها إلى لائحة العُقد المُزارة، وهكذا تصفت لائحة العُقد غير المُزارة:

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

---

🧩 الخطوة الأخيرة

آخر شيء الآن أن نطبق الخطوة الأخيرة التي ادخرتها للنهاية:

---

🔚 الخطوة الرابعة

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

---

🧭 لماذا عمود (العُقدة الأب)؟

لهذا السبب كان معنا عمود (العُقدة الأب)،
حتى نتتبع العُقد التي فيها حتى نصل للبداية،
ثم نعكسها فيظهر لنا الطريق.

---

🎯 التطبيق العملي

قلنا في البداية نريد التوجه إلى العُقدة (و) في أقصر طريق،
حسنًا، ما تكلفة العُقدة (و) في الجدول؟

نعم، أحسنت أيها المبعسس،
إنها ١٢.

---

🔍 تتبع الأب

وما العُقدة التي في عمود (العُقدة الأب)؟
ما العُقدة الأب للعُقدة (و)؟

إنها (هـ)
➡️ سنذهب إلى العُقدة (هـ):

اذهب الآن إلى العُقدة(هـ) وانظر ما العُقدة الأب لها؟ هي العُقدة(جـ):

نحن نقف الآن في العُقدة(جـ)، اذهب إلى الجدول وانظر ما العُقدة الأب لها؟ ستراها العُقدة(ب):

نحن نقف الآن في العُقدة (ب)، اذهب إلى الجدول وانظر ما العُقدة الأب لها؟ ستراها العُقدة (أ):

اذهب إلى الجدول وانظر ما العُقدة الأب لها؟

🎉 تهانينا!
وصلنا إلى البداية وعرفنا الطريق الأقصر!

---

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

تعلمنا:

• 🧮 كيف نحسب أقل تكلفة للوصول إلى كل عقدة،

• 🧭 ولماذا نحتاج عمود العقدة الأب لإعادة بناء المسار الكامل،

• ⚠️ وفهمنا الحدود التي تعمل فيها الخوارزمية،
  لا سيما فيما يتعلق بـ الأوزان السالبة والحلقات.

---

📝 التمرين

نهاية المقال!
حل التمرين التالي:

في كلّ واحد من هذه المِبيانات
احسب مجموع الأوزان على المسار الأقصر
الذي يصل من مكان البداية إلى مكان النهاية
(طبق خوارزمية ديكسترا):

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

نُحدِّثك في هذا المقال عن خوارزمية ديكسترا Dijkstra للبحث عن أقصر طريق؛ وهي وإن كانت أختًا لخوارزمية البحث المُتَّسِع Breadth-First Search وتشترك معها في الأصل، فإنها تمتاز عنها بميزةٍ ظاهرة وتغايرها في جوهرٍ دقيق ستراه اليوم. إن لم تقرأ مقالنا عن خوارزمية البحث المتسع فاذهب لقراءته مشكورًا:

https://bassye.org/grokking_algorithms_6_4/

وقبل الشروع بها يُستَحسن بي أن أقص لك طرفًا من سيرة واضع (مخترع) الخورازمية أيدسكر فيبِ دايكسترا Edsger Wybe Dijkstra (وهي باسمه)، ثم أتبعها بقصة طريفة عن نشأة الخوارزمية، ثم نلج إلى الخوارزمية بعون الله.

أيدسكر فيبِ دايكسترا

أيدِسكَر دايكسترا أيدسكر دايكسترا عالم رياضيات وحوسبة هولندي النشأة، من أوائل من أسهموا في وضع أسس علم الحوسبة الحديث، وقد وُلد في روتردام عام ١٩٣٠م، ونشأ في بيت علم ومعرفة، فترعرع على حب الحساب والمنطق، وأظهر في شبابه ميلًا إلى التفكير المنظم والتحليل الدقيق.

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

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

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

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

قصة وضع الخوارزمية

خذه الخوارزمية لم تخطر لذهن أيدسكر فيبِ دايكسترا بعد كد النظر وإتعاب الفكر، بل جاءت إلى العالم كوميض خاطف في لحظة هدوء وعفوية، لم يتكلفها!

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

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

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

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

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

---

قُصور خوارزمية البحث المتسع

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

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

أسرع طريق استغرق ٢٤ دقيقة (١٠+٥+٥+٤=٢٤)، أما خوارزمية البحث المتسع إن طبقناها فإنها ستبحث عن أقصر طريق، الذي هو أقل خطوات للوصول إلى الوجهة، أي ٤ + ٢١ + ٤ = ٢٩ دقيقة، فليس هو الأسرع (زمنيًا) بل الأقصر أو الأقل في الخطوات، لأننا نريد الوصول في وقت أقل لا أن نسير خطوات أقل!

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

لِمَ أخفقت خوارزمية البحث المتسع؟ أليست تعطينا الطريق الأقصر؟

المِبيان الموزون

سبب إخفاق خوارزمية البحث المتسع أنها لا تُطبَّق على المِبيان الموزون weighted graph، وقد تقدم بنا الكلام في أول مقالة في الفصل السادس وتحدثنا عن أنواع المِبيان، وذكرنا المِبيان الموزون.

فالمِبيان نوعان، مبيان عادي ومِبيان موزون.

المِبيان الموزون هو أن نعطي للشيء وزنًا، أي قيمة، وفي مثالنا السابق كان الزمن، لأننا نريد الأسرع، والسرعة تقاس بالمسافة المقطوعة في زمن. انظر المِبيان الموزون:

الرقم الذي عند كل وصلة edge هو زمن المسير لكل عقدة، فالمسير من مكان البداية إلى العقدة التالية يكون في ست دقائق، وهكذا كل مسلك في الصورة له زمن.

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

الخوارزمية التي تُطبَّق على المِبيان الموزون هي خوارزمية ديكسترا، ولها نهج يميزها عن أختها القاصرة عنها، ودونك تفصيله:

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

نهج خوارزمية ديكسترا المُتّبَع [على سبيل الإجمال ثم يتلوها التفصيل والمثال]:
١. نبحث أوّلًا عن أقرب عُقدة يمكن الوصول إليها بأقل زمن.
٢. ثم نراجع الطرق المؤدية إلى جيرانها، فإن وجدنا طريقًا أقرب ممّا سُجِّل، أثبتناه مكانه (إن لم تفهم فلا تبتئس، شرحها آتٍ).
٣. نكرر ما سبق لكل عُقدة في المِبيان حتى تتّضح كلفة الوصول إلى كلّ موضع.
٤. احسب زمن الطريق النهائي.

تفصيل كل خطوة في نهج الخوارزمية:

الخطوة الأولى: نبحث أوّلًا عن أقرب عُقدة يمكن الوصول إليها بأقل زمن.

نقف في البداية، ثم من هذا الموضع يتفرّع أمامك طريقان: طريقٌ يؤدي إلى الموضع أ، وطريقٌ آخر يؤدي إلى الموضع ب.
ونسأل: كم يستغرق الوصول إلى كلٍّ منهما؟

يستغرق ست دقائق إلى المكان أ، ودقيقتين إلى المكان ب،
أما سائر العُقَد فأنت لا تعرفها الآن، ولأن زمنها غير معلوم، نضع لكلٍّ منها قيمة كبيرة جدًّا هي المتناهية infinity (ولا تقل لا نهائية). وسبب وضعها أننا لا نعلم أين النهاية، فوضعنا لها قيمة اسمها الرياضي المتناهية، لأنها تتناهى إلى غاية غير معلومة!

إذن أقرب عقدة نصل إليها هي العقدة ب، لأنها لا تبعد إلا دقيقتين، وهو أقل زمن ممكن.
سنأخذ كل عقدة ونضعها في جدول ومعها الزمن:

(الوجهة) هي نقطة النهاية التي نود الوصول إليها بالخوارزمية بأسرع طريق.
انظر إذا طبقنا خوارزمية البحث المتسع، ستكون النتيجة (سبع دقائق):

الخطوة الثانية: عدل الكلفة لجيران هذه العقدة

احسب مقدار الوقت اللازم للوصول إلى كلِّ جار من جيران العقدة ب، وهي العقدة التي اخترناها في الخطوة الأولى. ثم انظر في كلِّ طريقٍ يتفرّع من ب، ودوّن ما يحتاجه اجتياز هذا الطريق من وقت، لتعرف أيَّ الطرق أقصر زمناً وأقلَّ كلفة.

بمعنى أننا سنمسك العقدة (ب) ونرى كم الوقت المستغرق للوصول إلى كل جار من جيران هذه العقدة.

للعقدة جارين هما:
(أ) والوقت للوصول إليه: ٣ دقائق
(النهاية): الوقت للوصول إاليها: خمس دقائق

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

الآن ما الذي قصدناه بقولنا: تعديل التكلفة لجيران هذه العقدة؟
الجدول السابق كان فيه العُقَد مع الوقت المُستَغرق، وقد كان: ست دقائق إلى (أ)، أما (النهاية) فكانت قيمتها متناهية.

أما في الخطوة الثانية عثرنا على:
١. طريق جديد إلى العُقدة (أ) يستغرق خمس دقائق،

٢. عرفنا أن الوقت المُستَغرق إلى (النهاية) كان سبع دقائق.
أما في الجدول فكانت (النهاية) قيمتها متناهية، لكننا سنعدلها في الجدول لتكون: ٧ دقائق، أما العُقدة (أ) سنعدلها من ٦ دقائق إلى ٥ دقائق.

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

الخطوة الثالثة: نكرر ما سبق لكل عُقدة في المِبيان حتى تتّضح كلفة الوصول إلى كلّ موضع.

تكرار الخطوة الأولى:

بما أننا قد فرغنا من العُقدة (ب) ولم يَبق لنا في المِبيان إلا العُقدة (أ) لم نجرب عليها فإننا سنجرب عليها!

سنأخذها ونرى جيرانها، وليس معها إلا جار واحد، هو الخط المشير إلى مكان (النهاية) ويستغرق دقيقة واحدة

ثم نضيف الرقم خمسة للواحد!
لأنك سلكت الطريق من البداية إلى (ب) في دقيقتين، ثم من (ب) إلى (أ) في ثلاث دقائق (٣+٢=٥)، ثم من (أ) إلى النهاية في دقيقة (٥+١=٦)، فالنتيجة ستة!

تكرر الخطوة الثانية:

نعدل الآن الكلفة لجيران العُقدة، وقد قلنا إنه جار للعُقدة (النهاية)، وقد كانت في الجدول قيمتها ٧، لكنها الآن صارت ستة، وبما أنها أقل من القيمة التي في الجدول فإننا سنعدلها لتصير ستة:

وها قد انتهينا من تطبيق الخوارزمية على كل عُقدة في المِبيان، ولم يتبقَ لنا أي عُقدة للتطبيق عليها، إذن نتوقف ونرى قيمة (النهاية)، وهي ستة، وهذه النتيجة النهائية!
عرفنا أقصر طريق بخوارزمية ديكسترا وكان في ست دقائق!

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

الحَلَقة في المِبيان

تحدث في الكتاب عن الحَلَقة في المِبيان، ومعناها أن تبدأ من نفس المكان وتعود إليه، فأنت في حَلَقة، أي دائرة، تبدأ من مكان وتنتهي إليه، فمكان الانطلاق هو مكان التوقف!

ثم ذكر المِبيان المُطلق والمِبيان الموجَّه (وقد شرحتهما لك في المقال السابق فراجعه)

بما أن كل عقدة تتصل بأختها وأختها تتصل بها فإنها تنشأ حَلَقة بينهما! انظر:

ثم قال وهنا أخطأ الكاتب: خوارزمية ديكسترا لا تعمل إلا على المِبيان الموجّه الخالي من الحلقات (DAG).

وهذا الكلام خطأ!

فخوارزمية ديكسترا لا تشترط أن يكون المِبيان موجّهًا، ولا أن يكون خاليًا من الحلقات، بل تعمل عملًا سليمًا على المِبيان الموجّه والمُطلق، سواء كان فيه حلقات أم لم يكن.
والحالة الوحيدة التي تُخفِق فيها خوارزمية ديكتسرا هي: (أن يكون الوزن بالسالب)، على كل وزن في المِبيان أن لا يكون سالبًا، وإنما موجب القيمة، فهذه الحالة الوحيدة التي تُخفِق فيها خوارزمية ديكسترا، أما ربطها بالمِبيان الموجَّه الخال من الحلقات (DAG) فخطأ.

لهذا يجب التنبيه إلى أن الخلل ليس في وجود حلقة، بل في وجود وزنٍ سالب؛ فهو وحده ما يُفسد نتائج الخوارزمية، وفي هذه الحالة (حالة الوزن السالب) نستعمل خوارزمية أخرى اسمها خوارزمية بيلمان–فورد Bellman–Ford مصممة للعمل على المِبيان الذي فيه وزن سالب.

---

المثال المكتمل

المثال السابق كان سهلًا، لأن العُقد في المِبيان كانت قليلة (عقدتان) ويَسهل تتبعها، لكن عندما يتعقد المِبيان سترى قصور المثال الأول وأنه لا يفهمك الخوارزمية بحق فهمها إلا بمثال لمِبيان معقد مثل هذا:

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

كما في المثال الأول، نبدأ بوضع كل العُقَد في جدول لمتابعة أقل تكلفة للوصول إليها (لكل عُقدة في المِبيان).لكن هذه المرة علينا إضافة عمود جديد في الجدول نسميه “العقدة السابقة” أو “العقدة الأب” Parent / Previous Node.
وغرض هذ العمود: تسجيل العقدة التي وصلنا منها إلى العقدة الحالية بأقل تكلفة، مثلا إذا وصلنا إلى العقدة (ب) عبر العقدة (أ) بأقل تكلفة، فإننا نسجل في خانة “العقدة الأب”: (أ)، لتخبرنا أننا أتينا إلى (ب) عبر العُقدة (أ).
هذه الإضافة مهمة حتى تتم الخوارزمية.

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

ثم سنضيف لائحتين، الأولى فيها العُقَد المُزارة، حتى لا نزور العُقَدة نفسها مرتين، واللائحة الثانية للعُقَد غير المُزارة، حتى نزورها كلها، لأنه كما تقدم، علينا تطبيق الخوارزمية على كل عُقدة في المِبيان.

تجهزنا الآن لتطبيق الخوارزمية، فهيا بنا!
لأذكرك بالخطوات الأربع:
١. نبحث أوّلًا عن أقرب عُقدة يمكن الوصول إليها بأقل زمن.
٢. ثم نراجع الطرق المؤدية إلى جيرانها، فإن وجدنا طريقًا أقرب ممّا سُجِّل، أثبتناه مكانه.
٣. نكرر ما سبق لكل عُقدة في المِبيان حتى تتّضح كلفة الوصول إلى كلّ موضع.
٤. احسب زمن الطريق النهائي.

نبدأ من مكان البداية وهو العُقدة (أ)، التي لها جارين هما: (ب) و(جـ)، قيمة الأولى ٢ والثانية ٨
انظر للجدول في الصورة، قيمة كل من (ب) و(جـ) هي المتناهية ∞، وقبل قليل عرفنا قيمة كل واحدة، إذن:
١. سنُعدل القيمة في الجدول
٢. نُزيل العُقدة (أ) من لائحة العُقد غير المُزارة ونضعها في لائحة العُقد المُزارة

العُقدة السوداء: عُقدة مُزارة قد فُرِغَ منها.

الآن نأخذ أقرب عقدة وهي الأقل كلفة (كما تقول الخطوة الأولى)، وهي العُقدة: (ب)، لأن قيمتها ٢ وهي أقل من ٨.

نبدأ من هذه العُقدة (ب) ونزور جيرانها وهما: العُقدة (د) والعُقدة (جـ):

ثم علينا إضافة ٢، وهي تكلفة العُقدة (ب)، إلى قيمة كلٍّ من العُقدة (د) والعُقدة (جـ)، أضفناها لأنها تمثل الطريق من بدايته، فأنت أتيت من العُقدة (أ) إلى العُقدة (ب) وكلفة الطريق ٢.

نتيجة الإضافة إلى العُقدة (د) = ٨
ونتيجة الإضافة إلى العُقدة (جـ) = ٧

بعد إضافة القيمة سنقارن القيم الجديدة (٨ و٧) بما كان معنا على الجدول، وقد كانت قيمة العُقدة (د) تساوي المتناهية ∞،والعُقدة (جـ) كانت ٨، والنتيجة الحالية هي: ٧.

والسبعة أقل من الثمانية، والخطوة الثانية تقول: (ثم نراجع الطرق المؤدية إلى جيرانها، فإن وجدنا طريقًا أقرب ممّا سُجِّل، أثبتناه مكانه)، وقد عثرنا على طريق أقصر من الطريق القديم الذي كان ثمانية، لهذا وجب حذفه وكتابة القيمة الجديدة لأنها أقصر!

كما ترى:
١. عدلنا قيمة العُقدة (د) والعُقدة (جـ)، الأولى من المتناهية إلى ٨، والثانية من ٨ إلى سبعة
٢. عدلنا عمود (العُقدة الأب) لكُلٍّ من العُقدة (د) والعُقدة (جـ) وجعلناها (ب)، لأننا أتينا منها إليهما.
٣. ثم أضفنا العُقدة (ب) إلى لائحة العُقد المُزارة، وهكذا لن نزورها مرة ثانية، وقد جعلت لونها بالأسود إشارة على أننا قد فرغنا منها.

الآن نطبق الخطوة الأولى مرة ثانية: (نبحث أوّلًا عن أقرب عُقدة يمكن الوصول إليها بأقل زمن “تكلفة”)، أي سنبحث عن الأقل تكلفة من بين العُقد التي هي جيران للعُقدة (ب): العُقدة (د) والعُقدة (جـ)، وهي العُقدة (جـ):

سنضيف القيمة ٧، وهي قيمة العُقدة (جـ)، المستخرجة من الطريق المسلوك من مكان البداية: من (أ) إلى (ب) = ٢، ومن (ب) إلى (جـ) = ٥، و٥+٢ = ٧

سنضيف القيمة ٧ إلى العُقدة (د) والعُقدة (هـ):
العُقدة (د) = ٣ + ٧ = ١٠
العُقدة (هـ) = ٢ + ٧ = ٩

سنأخذ هذه القيم ونضيفها إلى الجدول، ونلاحظ أول شيء أن كلفة العُقدة (د) تساوي ١٠، وهي أكبر من كلفتها على الجدول، لهذا لن نغيرها، سنغيرها إذا كان أقل، أما إذا كانت أكثر فلن نفعل!
أما العُقدة (هـ) سنغيرها من المتناهية ∞ إلى ٩، وثم نعدل عمود (العُقدة الأب) لها، أما العُقدة (د) ستبقى كما هي بلا تغيير، فلم نجد شيئًا نغيره لها:

كما ترى:
١. عدلنا كلفة العُقدة (هـ) من المتناهية إلى ٩
٢. عدلنا عمود (العُقدة الأب)للعُقدة (هـ) وجعلناها (جـ)، لأننا أتينا منها إليها.
٣. ثم أضفنا العُقدة (جـ) إلى لائحة العُقد المُزارة، وهكذا لن نزورها مرة ثانية، وقد جعلت لونها بالأسود إشارة على أننا قد فرغنا منها.

بعد تعديل الجدول = نرى أي العُقد من (د) و(هـ) هي الأقل كلفة ونأخذها لنطبق عليها ما طبقناها على أخواتها:
العُقدة (د) = ٨
العُقدة (هـ) = ٩
إذن سنأخذ العُقدة (د)، ونضيف إلى جيرانها القيمة ٨:

إضافة القيمة ٨ إلى كل عُقدة:
العُقدة (و) = ٩ + ٨ = ١٧
العُقدة (هـ) = ١ + ٨ = ٩

كلفة العُقدة (هـ) ما زالت هي القديمة، فلن نعدل في الجدول شيئًا
أما كلفة العُقدة (و) فقد كانت المتناهية ∞ أما الكلفة الجديدة فهي ١٧، وهي أقل من المتناهية، لهذا سنعدل كلفتها وسنعدل عمود (العُقدة الأب)، ثم نضيف العُقدة (د) إلى لائحة العُقد المُزارة:

الآن نأخذ أقل العُقد كلفة، العُقد المجاورة للعُقدة (د) وهما: العُقدة (و) وكلفتها ١٧، والعُقدة (هـ) وكلفتها ٩، والتسعة أصغر إذن سنأخذها ونطبق عليها ما سبق!

سنضيف قيمة ٩، وهي قيمة العُقدة (هـ) التي توضع المسار الذي سرنا فيه إليها، ثم بعد الإضافة سنرى هل نعدل الجدول أم لا؟
سنعدل الجدول لأن ٩ + ٣ = ١٢، والتكلفة القديمة للعُقدة (و) كانت ١٧، والنتيجة الجديدة هي ١٢، لذا سنعدلها إلى ١٢، ونعد عمود (العُقدة الأب) ليكون (هـ).
ثم سننقل العُقدة (هـ) إلى لائحة العُقد المُزارة:

تبقى معنا عُقدة واحدة هي العُقدة (و)، وهي نفس العُقدة التي نريد الوصول لها، إنها الوجهة. ولأنها لا تملك أي جيران فإننا سنتوقف هنا ونضيفها إلى لائحة العُقد المُزارة، وهكذا تصفت لائحة العُقد غير المُزارة:

وقد انتهينا من تطبيقها على كل عُقدة، فكيف نستخرج الطريق الذي علينا أن نسلكه حتى نصل للوجهة يا مبعسس؟
آخر شيء الآن أن نطبق الخطوة الأخيرة التي ادخرتها للنهاية:

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

لهذا السبب كان معنا عمود (العُقدة الأب)، حتى نتتبع العُقد التي فيها حتى نصل للبداية ثم نعكسها فيظهر لنا الطريق.
قلنا في البداية نريد التوجه إلى العُقدة (و) في أقصر طريق، حسنًا، ما تكلفة العُقدة (و) في الجدول؟
نعم، أحسنت أيها المبعسس، إنها ١٢
وما العُقدة التي في عمود (العُقدة الأب)؟ ما العُقدة الأب للعُقدة (و)؟
إنها (هـ) = سنذهب إلى العُقدة(هـ):

اذهب الآن إلى العُقدة(هـ) وانظر ما العُقدة الأب لها؟ هي العُقدة(جـ):

نحن نقف الآن في العُقدة(جـ)، اذهب إلى الجدول وانظر ما العُقدة الأب لها؟ ستراها العُقدة(ب):

نحن نقف الآن في العُقدة (ب)، اذهب إلى الجدول وانظر ما العُقدة الأب لها؟ ستراها العُقدة (أ):

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

---

التمرين

---

نهاية المقال! حل التمرين التالي:
في كلّ واحد من هذه المِبيانات احسب مجموع الأوزان على المسار الأقصر الذي يصل من مكان البداية إلى مكان النهاية (طبق خوارزمية ديكسترا):

ختامًا لا تنسونا من دعائكم 

ها قد وصلنا إلى نهاية المقال، وها أنا أخط بقلمي الخطوط الأخيرة لهذا المقال الشائق، وأرجو أنني قد وفّقت في الشرح.

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