خوارزمية Dijkstra لإيجاد أقصر مسار
حين تبدأ رحلة تعلّم الخوارزميات، ستجد أن بعض الأفكار تبدو في البداية بسيطة جدًا، ثم تكتشف لاحقًا أنها من أكثر الأدوات التي تُستخدم في العالم الحقيقي. خوارزمية Dijkstra واحدة من هذه الأفكار. قد تُقرأ في كتاب خوارزميات على أنها طريقة لإيجاد أقصر مسار في رسم بياني، لكن حقيقتها أوسع بكثير من ذلك. إنها أسلوب تفكير كامل في التعامل مع الشبكات، الطرق، العلاقات، التكاليف، والقرارات المثلى. هي الخوارزمية التي تقف وراء كثير من الأنظمة التي تبدو لنا يوميًا طبيعية وبديهية: اقتراح أفضل طريق في تطبيق خرائط، حساب أقل تكلفة نقل، إيجاد أقصر سلسلة من الانتقالات بين نقاط، وحتى بعض مشكلات التخطيط والتحسين في البرمجة والمجالات الصناعية.
ما يميّز Dijkstra ليس فقط أنها مشهورة، بل أنها تمثل واحدًا من أجمل نماذج “الاستراتيجية الجشعة” في علوم الحاسوب. الفكرة الأساسية فيها ليست معقدة: ابدأ من نقطة معينة، ثم توسّع نحو أقرب نقطة غير محسومة، وكرّر ذلك حتى تصل إلى كل النقاط الممكنة. لكن خلف هذا الوصف البسيط يوجد منطق دقيق جدًا يضمن أن القرار الذي يبدو “محليًا” في كل خطوة يؤدي بالفعل إلى الحل “الأفضل عالميًا” عندما تكون الأوزان غير سالبة. هذه النقطة الأخيرة مهمة للغاية، لأن الخوارزمية لا تعمل بشكل صحيح إذا وُجدت أوزان سالبة على الحواف. ولذلك، فإن فهمها لا يعني فقط حفظ خطواتها، بل فهم لماذا تنجح، ومتى تنجح، ومتى يجب أن تبحث عن بديل مثل Bellman-Ford أو Floyd-Warshall أو غيرهما.
ما هي خوارزمية Dijkstra؟
خوارزمية Dijkstra هي خوارزمية تُستخدم لإيجاد أقصر مسار من عقدة بداية واحدة إلى جميع العقد الأخرى في رسم بياني ذو أوزان غير سالبة. وإذا أردنا أن نقولها بشكل أبسط، فهي تبحث عن “أقل تكلفة” للوصول من نقطة الانطلاق إلى كل نقطة يمكن الوصول إليها. قد تكون هذه التكلفة مسافة، زمنًا، سعرًا، عدد خطوات، أو أي قيمة موجبة تمثل “ثمن” الانتقال من عقدة إلى أخرى.
لنفترض أن لديك مدينة مليئة بالطرق، وكل طريق بين تقاطعين له طول معين. إذا أردت أن تعرف أقصر طريق من منزلك إلى كل الأماكن الأخرى، فخوارزمية Dijkstra ستعطيك الجواب بكفاءة عالية، بشرط أن تكون أطوال الطرق غير سالبة، وهو أمر طبيعي في هذا المثال. في الرسم البياني، تُسمى الأماكن بالعُقد أو vertices، وتُسمى الطرق بالحواف أو edges، ولكل حافة وزن يعبّر عن التكلفة.
الجميل في Dijkstra أنها لا تحتاج إلى تجربة جميع المسارات الممكنة. وهذا ما يجعلها عملية جدًا. بدلاً من ذلك، تعتمد على فكرة ذكية: في كل مرحلة، تختار العقدة الأقرب التي لم يتم تثبيت مسافتها بعد، ثم تحدّث تقديرات المسافات للعقد المجاورة لها. هذه العملية المستمرة تشبه قليلًا السير بخطوات واثقة نحو الهدف الأقرب، ثم توسيع دائرة المعرفة شيئًا فشيئًا حتى تشمل كل الشبكة.
لماذا نحتاجها أصلًا؟
قد يبدو السؤال بسيطًا، لكن الإجابة تكشف أهمية الخوارزمية. في الحياة الواقعية، هناك الكثير من المشكلات التي يمكن صياغتها على هيئة رسم بياني. عندما تنتقل من صفحة إلى صفحة عبر روابط، أو من مدينة إلى مدينة، أو من خادم إلى خادم في شبكة، أو من عملية إلى عملية داخل نظام، فغالبًا أنت تتحرك على “عقد” مرتبطة بـ”حواف”. كل حافة لها تكلفة. وقد تكون هذه التكلفة وقتًا أو جهدًا أو مالًا أو احتمال خطأ.
من دون خوارزمية مثل Dijkstra، قد تضطر إلى تجربة عدد هائل من المسارات، وهذا مكلف جدًا. عدد المسارات الممكنة في رسم بياني قد ينفجر بسرعة كبيرة، خاصة إذا كان الرسم كبيرًا أو كثيفًا. Dijkstra تساعدنا على تجنب هذا الانفجار عبر أسلوب منظم ومضمون. لهذا السبب تُدرّس هذه الخوارزمية في بداية دراسة الرسوم البيانية، ولها حضور قوي في التطبيقات العملية، وفي المقابلات التقنية، وفي مسابقات البرمجة، وفي أبحاث التحسين.
الفكرة الأساسية وراء الخوارزمية
لنحاول الآن أن نفهم Dijkstra بعيدًا عن التعريف الرسمي الصلب. تخيّل أنك تقف في نقطة بداية، وترغب في معرفة أقصر طريق إلى كل مكان آخر. ما الذي ستفعله بشكل بديهي؟ ستبدأ بمسافة صفر إلى نفسك، وبقية النقاط تعتبرها “بعيدة جدًا” في البداية. ثم تنظر إلى الجيران المباشرين، وتحسب كلفة الوصول إليهم. بعد ذلك تختار من بين كل النقاط التي تعرف مسافتها المؤقتة، النقطة ذات المسافة الأصغر، لأنها الأكثر جدوى الآن، وتثبت أنها فعلًا الأقصر. ثم تنطلق منها إلى جيرانها، وتحاول تحسين تقديراتك لبقية العقد.
هذه الفكرة تُسمى greedy choice، أي “الاختيار الجشع”، لأنك في كل مرة تختار ما يبدو أفضل محليًا. ما يجعل هذا الأسلوب صحيحًا هنا هو أن الأوزان غير سالبة. عندما تختار العقدة ذات المسافة الأقل غير المثبتة، لا يمكن لطريق لاحق أن يفاجئك ويجعلها أقصر، لأن أي طريق جديد سيضيف أوزانًا إضافية لا تقل عن الصفر. لذلك، فإن أقصر مسافة وصلت إليها الآن تبقى الأقصر فعلًا. هذه هي روح الخوارزمية كلها.
متى تعمل ومتى لا تعمل؟
هذه نقطة مهمة جدًا ولا ينبغي تجاهلها. Dijkstra تعمل بشكل صحيح عندما تكون جميع الأوزان غير سالبة. إذا كانت هناك حواف ذات أوزان سالبة، فقد تفشل في إعطاء الحل الصحيح. السبب أن منطق “ما ثبت الآن لن يتغير لاحقًا” يتكسّر عندما يمكن لمسار آخر أن يقلل التكلفة بعد خطوات مستقبلية ذات وزن سلبي.
لهذا، إذا كانت لديك أوزان سالبة، فغالبًا ستفكر في Bellman-Ford، وهي أبطأ لكنها تتعامل مع السالب، أو في أساليب أخرى بحسب المشكلة. أما إذا كانت الأوزان غير سالبة، فـ Dijkstra غالبًا هي الخيار الأفضل من حيث الأناقة والسرعة وسهولة التطبيق.
التمثيل البياني: كيف نفهم المشكلة؟
قبل أن نكتب أي سطر برمجي، يجب أن نفهم شكل البيانات. الرسم البياني يمكن أن يكون موجهًا أو غير موجه. في الرسم غير الموجه، إذا كنت تستطيع الذهاب من A إلى B، فغالبًا تستطيع الذهاب من B إلى A بنفس التكلفة، أو بتكلفة أخرى حسب النموذج. أما في الرسم الموجه، فالاتجاه مهم؛ قد يوجد طريق من A إلى B ولا يوجد بالعكس.
تمثيل الرسم البياني برمجيًا غالبًا يكون باستخدام قائمة مجاورات adjacency list، لأنها فعّالة جدًا في التخزين، خاصة إذا كان الرسم sparse أي قليل الحواف مقارنة بعدد العقد. أما إذا كان الرسم dense، فقد تكون المصفوفة adjacency matrix مناسبة في بعض الحالات، لكن Dijkstra غالبًا تُستخدم مع قائمة المجاورات وpriority queue للحصول على أداء أفضل.
لنفرض أن لدينا العقد التالية: A، B، C، D، E. والوزن بين العقد قد يكون 2، 5، 1، إلخ. في البداية، نضع المسافة إلى A = 0 إذا كانت A هي نقطة الانطلاق، وباقي العقد = لا نهائي. ثم نبدأ التحديث. هذه “اللا نهائية” ليست رقمًا حقيقيًا في الخوارزمية، بل قيمة تمثيلية كبيرة جدًا أو float('inf') في Python مثلًا.
مثال بسيط جدًا قبل الدخول في التفاصيل
تخيّل الرسم التالي:
A إلى B = 4
A إلى C = 2
B إلى C = 1
B إلى D = 5
C إلى D = 8
C إلى E = 10
D إلى E = 2
E إلى D = 2
إذا بدأت من A، فالمسافة إلى A تساوي 0. إلى B هي 4، وإلى C هي 2. إذن العقدة الأقرب الآن هي C. من C، قد تجد طريقًا إلى B بتكلفة 2 + 1 = 3، وهذا أفضل من 4، فتحدّث المسافة إلى B. وقد تجد طريقًا إلى D بتكلفة 10، وإلى E بتكلفة 12. بعد ذلك تصبح B هي الأقرب غير المثبتة بمسافة 3، ومن B قد تجد طريقًا إلى D بتكلفة 3 + 5 = 8، وهو أفضل من 10. ثم تتابع حتى تصل لكل العقد.
هذا المثال البسيط يوضح لماذا الخوارزمية قوية: هي لا تختار المسار النهائي مباشرة، بل تبني مجموعة من أفضل التقديرات، ثم تحسنها تدريجيًا. ليس الهدف أن تتوقع كل شيء من البداية، بل أن تحتفظ بأفضل ما تعرفه حاليًا، وتحدّثه كلما ظهر شيء أفضل.
الخطوات الرسمية للخوارزمية
رغم أن الفكرة تبدو intuitive، إلا أن الصياغة الرسمية تساعدنا على تثبيت المعنى:
عيّن المسافة إلى العقدة المصدر = 0.
عيّن المسافة إلى جميع العقد الأخرى = لا نهائي.
ضع العقدة المصدر في بنية بيانات تساعدك على استخراج العقدة ذات المسافة الأصغر بسرعة.
بينما توجد عقد لم تُعالج بعد:
استخرج العقدة ذات أصغر مسافة مؤقتة.
اعتبر أن هذه المسافة أصبحت نهائية.
مرّ على جيرانها.
إذا وجدت طريقًا عبر هذه العقدة يعطي مسافة أقل إلى جارٍ ما، فحدّث المسافة.
استمر حتى تنتهي كل العقد الممكن الوصول إليها.
في التطبيق العملي، بنية البيانات الأكثر شيوعًا هي min-heap أو priority queue، لأنك تحتاج باستمرار إلى إيجاد أقل مسافة مؤقتة بسرعة. من دونها، ستصبح الخوارزمية أبطأ بكثير.
لماذا نستخدم Priority Queue؟
لو حاولت كل مرة أن تبحث يدويًا في قائمة المسافات عن أصغر قيمة غير معالجة، فستدفع تكلفة كبيرة. في أسوأ الحالات، قد تصبح العملية من رتبة O(V^2) إذا كان عدد العقد كبيرًا. لكن باستخدام priority queue، يمكنك استخراج العقدة الأقرب بسرعة أكبر، مما يجعل الخوارزمية أكثر كفاءة على الرسوم الكبيرة والمتناثرة.
الفرق بين الخوارزمية البسيطة والخوارزمية المحسنة بالبنية المناسبة يشبه الفرق بين البحث في كومة أوراق بيدك وبين ترتيبها في درج منظم بعلامات واضحة. في الحالتين يمكنك الوصول، لكن في الثانية تصل أسرع وبأقل جهد.
إثبات الفكرة بشكل حدسي
ليس من الضروري أن نحول كل شيء إلى برهان رياضي ثقيل كي نفهم لماذا Dijkstra صحيحة. لكن من المفيد جدًا أن نرى الحدس.
عندما تختار العقدة ذات أصغر مسافة مؤقتة من بين العقد غير المثبتة، فأنت تقول ضمنيًا: “أنا واثق أن هذا هو أقصر طريق إليها”. لماذا؟ لأن أي مسار آخر سيصل إليها عبر عقد أخرى لم تُثبت بعد أو عبر مسار أطول. وبما أن كل الأوزان غير سالبة، فإضافة خطوات جديدة لا يمكن أن تجعل المسار أقصر من المسافة الأقل التي لديك الآن. لذلك، حين تصل إلى أصغر قيمة، لا يوجد طريق لاحق قادر على تحسينها.
هذا الاستنتاج هو قلب الخوارزمية. لو كانت الأوزان سالبة، فربما يأتي طريق لاحق ويخفض الكلفة بعد أن كنت قد ثبّت العقدة، وهذا ما يجعل الخوارزمية غير صالحة في تلك الحالة. لكن مع الأوزان غير السالبة، المنطق متين.
التعقيد الزمني وتعقيد الذاكرة
من أشهر الأسئلة حول Dijkstra: كم تستغرق من الوقت؟ الجواب يعتمد على طريقة التنفيذ.
إذا استعملت مصفوفة للبحث عن أصغر عقدة غير معالجة في كل مرة، فالتعقيد قد يصل إلى O(V^2)، حيث V هو عدد العقد. هذا قد يكون مقبولًا في الرسوم الصغيرة أو الكثيفة جدًا، لكنه ليس الأفضل عادة.
أما إذا استعملت priority queue مع adjacency list، فغالبًا تحصل على تعقيد قريب من O((V + E) log V)، أو أحيانًا يُكتب O(E log V) في التحليل الشائع، حيث E هو عدد الحواف. هذا أفضل بكثير للرسوم الكبيرة والمتناثرة. أما الذاكرة، فغالبًا تحتاج إلى O(V + E) لتمثيل الرسم، بالإضافة إلى بعض المساحة للمسافات والحالات والبنية المساعدة.
هذه الأرقام ليست مجرد تفاصيل نظرية. في المشاريع الواقعية، الفرق بين O(V^2) و O(E log V) قد يقرر ما إذا كان البرنامج سيعمل بسلاسة أو سيصبح بطيئًا جدًا.
خوارزمية Dijkstra خطوة بخطوة على مثال عملي
لنأخذ مثالًا آخر أكثر وضوحًا. لدينا عقد: S، A، B، C، D، E. والنقاط والوزن كما يلي:
S → A = 7
S → B = 2
S → C = 3
A → B = 3
A → D = 4
B → D = 4
B → E = 6
C → B = 1
C → E = 8
D → E = 2
نبدأ من S.
المسافات الابتدائية:
S = 0
A = ∞
B = ∞
C = ∞
D = ∞
E = ∞
ننظر إلى جيران S:
A تصبح 7
B تصبح 2
C تصبح 3
أصغر مسافة الآن هي B = 2. نثبت B.
من B:
D قد تصبح 2 + 4 = 6
E قد تصبح 2 + 6 = 8
الآن لدينا:
A = 7
B = 2 (مثبتة)
C = 3
D = 6
E = 8
أصغر مسافة غير مثبتة هي C = 3. نثبت C.
من C:
B عبر C تصبح 3 + 1 = 4، وهذا لا يحسن 2
E عبر C تصبح 3 + 8 = 11، وهذا لا يحسن 8
الآن:
A = 7
D = 6
E = 8
أصغر مسافة غير مثبتة هي D = 6. نثبت D.
من D:
E عبر D تصبح 6 + 2 = 8، وهي مساوية للقيمة الحالية، فلا تغيير مهم
الآن:
A = 7
E = 8
نثبت A = 7.
من A:
B عبر A تصبح 10، لا تحسن
D عبر A تصبح 11، لا تحسن
أخيرًا E = 8.
النتيجة النهائية:
S = 0
B = 2
C = 3
D = 6
A = 7
E = 8
لاحظ كيف لم نحاول كل المسارات، ومع ذلك حصلنا على الإجابة الصحيحة.
كيف نستعيد المسار نفسه وليس فقط المسافة؟
في كثير من الأحيان، لا يكفي أن تعرف أن المسافة إلى E هي 8. أنت تريد أن تعرف أيضًا: ما الطريق الذي أوصلنا إلى هذه القيمة؟ لذلك، في التنفيذ العملي، نحتفظ بمصفوفة أو قاموس previous أو parent، تخزن العقدة السابقة التي حسّنت المسافة الحالية.
عندما تحدّث مسافة جار من خلال عقدة حالية، لا تكتفي بحفظ رقم المسافة الجديد، بل احفظ أيضًا أن هذا الجار جاء من تلك العقدة. وفي النهاية، لو أردت استخراج المسار من المصدر إلى الهدف، تبدأ من الهدف وتعود عبر previous حتى تصل إلى المصدر، ثم تعكس الترتيب.
هذه الخطوة شديدة الأهمية في التطبيقات العملية. لأن المستخدم النهائي غالبًا لا يريد فقط “كم تساوي المسافة”، بل يريد أيضًا “ما هو الطريق”.
تطبيق Dijkstra بلغة Python
فيما يلي تطبيق واضح ومناسب للفهم، باستخدام heapq كبنية priority queue:
import heapq
def dijkstra(graph, start):
# graph: dict of node -> list of (neighbor, weight)
distances = {node: float('inf') for node in graph}
previous = {node: None for node in graph}
distances[start] = 0
pq = [(0, start)] # (distance, node)
while pq:
current_distance, current_node = heapq.heappop(pq)
# إذا كانت القيمة المستخرجة قديمة، نتجاوزها
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current_node
heapq.heappush(pq, (distance, neighbor))
return distances, previous
def reconstruct_path(previous, start, end):
path = []
current = end
while current is not None:
path.append(current)
if current == start:
break
current = previous[current]
if not path or path[-1] != start:
return [] # لا يوجد مسار
return path[::-1]
graph = {
"S": [("A", 7), ("B", 2), ("C", 3)],
"A": [("B", 3), ("D", 4)],
"B": [("D", 4), ("E", 6)],
"C": [("B", 1), ("E", 8)],
"D": [("E", 2)],
"E": []
}
distances, previous = dijkstra(graph, "S")
print("Distances:", distances)
print("Path to E:", reconstruct_path(previous, "S", "E"))
هذا المثال يوضح الفكرة بشكل عملي. لاحظ أننا استخدمنا float('inf') لتمثيل اللانهاية، واستعملنا heapq لاستخراج أصغر مسافة. كما أننا تجاهلنا الإدخالات القديمة في الـ priority queue عندما نكتشف أن القيمة المستخرجة لم تعد مطابقة لأفضل مسافة محفوظة. هذا أسلوب شائع جدًا لأن heapq في Python لا يتيح التحديث المباشر للعناصر داخل الكومة بسهولة، ولذلك نسمح بوجود نسخ متعددة، ثم نتجاهل غير الصالح منها.
شرح كود Python بعمق
الجزء الأول من الكود يبني القواميس distances و previous. كل عقدة تبدأ بمسافة لا نهائية ما عدا نقطة البداية، التي تبدأ بصفر. ثم نضع (0, start) في الطابور.
داخل الحلقة، نستخرج أصغر مسافة مؤقتة. إذا كانت هذه القيمة أكبر من القيمة الحالية المخزنة، فهذا يعني أن لدينا إدخالًا قديمًا، فنتركه. بعد ذلك نستعرض الجيران. إذا وجدنا مسارًا أقصر عبر العقدة الحالية إلى جارٍ ما، نحدّث المسافة ونحفظ previous ونضيف الجار إلى الـ heap.
الجزء الأخير، reconstruct_path، يجمع المسار من النهاية إلى البداية. هذه الوظيفة بسيطة لكنها مهمة جدًا؛ فهي تحوّل نتائج الخوارزمية من مجرد أرقام إلى مسار مفهوم يمكن عرضه للمستخدم.
تطبيق Dijkstra بلغة JavaScript
الآن لننتقل إلى JavaScript. في JS لا توجد priority queue مدمجة قياسية في اللغة نفسها، لذلك يمكننا كتابة نسخة بسيطة من min-priority queue باستخدام مصفوفة مرتبة، أو استخدام heap مخصص. هنا سأعطيك مثالًا واضحًا وسهل الفهم باستخدام heap بسيط:
class MinHeap {
constructor() {
this.heap = [];
}
push(item) {
this.heap.push(item);
this.bubbleUp(this.heap.length - 1);
}
bubbleUp(index) {
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
if (this.heap[parent][0] <= this.heap[index][0]) break;
[this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
index = parent;
}
}
pop() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const top = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown(0);
return top;
}
bubbleDown(index) {
const length = this.heap.length;
while (true) {
let smallest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
if (left < length && this.heap[left][0] < this.heap[smallest][0]) {
smallest = left;
}
if (right < length && this.heap[right][0] < this.heap[smallest][0]) {
smallest = right;
}
if (smallest === index) break;
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
index = smallest;
}
}
isEmpty() {
return this.heap.length === 0;
}
}
function dijkstra(graph, start) {
const distances = {};
const previous = {};
const nodes = Object.keys(graph);
for (const node of nodes) {
distances[node] = Infinity;
previous[node] = null;
}
distances[start] = 0;
const pq = new MinHeap();
pq.push([0, start]);
while (!pq.isEmpty()) {
const [currentDistance, currentNode] = pq.pop();
if (currentDistance > distances[currentNode]) {
continue;
}
for (const [neighbor, weight] of graph[currentNode]) {
const distance = currentDistance + weight;
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
previous[neighbor] = currentNode;
pq.push([distance, neighbor]);
}
}
}
return { distances, previous };
}
function reconstructPath(previous, start, end) {
const path = [];
let current = end;
while (current !== null) {
path.push(current);
if (current === start) break;
current = previous[current];
}
if (path[path.length - 1] !== start) {
return [];
}
return path.reverse();
}
const graph = {
S: [["A", 7], ["B", 2], ["C", 3]],
A: [["B", 3], ["D", 4]],
B: [["D", 4], ["E", 6]],
C: [["B", 1], ["E", 8]],
D: [["E", 2]],
E: []
};
const result = dijkstra(graph, "S");
console.log(result.distances);
console.log(reconstructPath(result.previous, "S", "E"));
هذا المثال مفيد جدًا إذا كنت تعمل في بيئة JavaScript أو Node.js أو حتى داخل مشروع ويب. وبالمناسبة، يمكن توسيع الفكرة بسهولة لتناسب TypeScript بإضافة أنواع واضحة للعُقد والأوزان.
لماذا نفضل قائمة المجاورات؟
من الناحية العملية، قائمة المجاورات هي التمثيل الأكثر شيوعًا مع Dijkstra، خاصةً عندما يكون الرسم البياني كبيرًا لكنه ليس كثيفًا جدًا. كل عقدة تخزن فقط الجيران المرتبطين بها مباشرة، وبالتالي لا تضيع مساحة على الحواف غير الموجودة. أما المصفوفة، فتجبرك على تخصيص مساحة لكل زوج ممكن من العقد، حتى لو لم توجد حافة بينهما.
هذا الفارق مهم عندما يكون عدد العقد كبيرًا. لو كان لديك 100,000 عقدة، فإن المصفوفة قد تصبح ضخمة جدًا وغير عملية. بينما قائمة المجاورات تظل أكثر مرونة، وتسمح للخوارزمية أن تعمل بكفاءة أفضل.
حالات استخدام حقيقية
قد تتساءل: هل هذه الخوارزمية مجرد تمرين أكاديمي؟ الحقيقة أنها تُستخدم في مجالات كثيرة. من أشهرها:
أنظمة الملاحة والخرائط.
حساب أقل تكلفة في الشبكات.
التوجيه routing في الشبكات الحاسوبية.
ألعاب الفيديو، لإيجاد مسارات الشخصيات أو الأعداء.
التخطيط اللوجستي.
تحليل العلاقات في بعض النماذج الشبكية.
أي مسألة يمكن صياغتها على أنها أقصر طريق في رسم بياني ذي أوزان غير سالبة.
السبب في هذا الانتشار أنها بسيطة نسبيًا، مضمونة، وسريعة عندما تُنفذ بشكل صحيح. لهذا ستجدها حاضرة في الكتب، والمشروعات، والكود الإنتاجي، والأسئلة التقنية.
الفرق بين Dijkstra و BFS
هنا يقع كثير من المبتدئين في لبس شائع. خوارزمية BFS ليست نفسها Dijkstra، لكنها قد تبدو قريبة في بعض الحالات. BFS تصلح لإيجاد أقصر مسار عندما تكون جميع الأوزان متساوية، أو عندما تكون كل حافة تكلفتها 1. في هذه الحالة، يكفي أن تمشي مستوى بمستوى، لأن كل خطوة لها نفس الثمن.
أما Dijkstra فهي تتعامل مع أوزان مختلفة غير سالبة. ولذلك فهي أكثر عمومية. لو كانت كل الأوزان تساوي 1، فـ BFS أبسط وأسرع غالبًا. لكن عندما تختلف الأوزان، تصبح Dijkstra هي الحل المناسب.
هذا التمييز مهم جدًا في المقابلات التقنية، لأن البعض يستخدم Dijkstra حتى عندما تكون BFS هي الأنسب. اختيار الأداة المناسبة جزء من المهارة نفسها.
الفرق بين Dijkstra و Bellman-Ford
إذا كانت Dijkstra هي الخوارزمية السريعة للأوزان غير السالبة، فإن Bellman-Ford هي الخوارزمية الأكثر مرونة عندما توجد أوزان سالبة. لكنها أبطأ غالبًا. Dijkstra تعتمد على فكرة التثبيت النهائي المبكر للعقدة الأقرب، وهذا لا يناسب السالب. Bellman-Ford من جهتها تقوم بعملية استرخاء repeated relaxation على جميع الحواف عدة مرات، ولذلك فهي تستطيع التعامل مع بعض المشكلات التي لا تستطيع Dijkstra التعامل معها.
إذا كنت تعمل على مشكلة ذات أوزان غير سالبة، فلا داعي لتعقيد نفسك بـ Bellman-Ford. أما إذا كان هناك سالب أو احتمال لوجود دورة سالبة، فهنا يجب أن تنتبه وتختار الخوارزمية الصحيحة.
مفهوم Relaxation أو التحديث التدريجي
أحد أهم المفاهيم التي يجب أن تفهمها في Dijkstra هو relaxation. هذا المصطلح يعني ببساطة: “هل يمكنني تحسين المسافة المعروفة إلى هذه العقدة إذا مررت عبر عقدة أخرى؟” إذا كانت الإجابة نعم، فنقوم بالتحديث. وإذا كانت لا، نترك القيمة كما هي.
الفكرة بسيطة للغاية، لكن قوتها كبيرة. الخوارزمية كلها مبنية على سلسلة لا تنتهي من محاولات التحسين الصغيرة. نحن لا نحاول أن نعرف كل شيء دفعة واحدة، بل نحسن التقديرات تدريجيًا إلى أن لا يبقى أي تحسين ممكن.
هذا النهج شائع في خوارزميات كثيرة، وليس Dijkstra فقط. وهو من أجمل مبادئ علوم الحاسوب: بناء حل كبير من قرارات محلية صغيرة، بشرط أن تكون هذه القرارات صحيحة ومصممة بعناية.
أخطاء شائعة عند تطبيق Dijkstra
هناك مجموعة من الأخطاء تتكرر كثيرًا، خاصة عند كتابة الخوارزمية لأول مرة:
أولًا، نسيان أن الخوارزمية لا تعمل بشكل صحيح مع الأوزان السالبة. هذا الخطأ شائع جدًا.
ثانيًا، نسيان تحديث previous أو parent، ثم التعرّض لاحقًا لعجز عن استرجاع المسار.
ثالثًا، عدم تجاهل العناصر القديمة في الـ priority queue عندما لا يكون هناك decrease-key مباشر.
رابعًا، استخدام BFS بدل Dijkstra في مشكلة ذات أوزان مختلفة، ثم الحصول على نتائج خاطئة.
خامسًا، التعامل مع الرسم البياني على أنه غير موجه بينما هو موجه، أو العكس. هذا يغيّر النتيجة بالكامل.
سادسًا، نسيان أن بعض العقد قد تكون غير قابلة للوصول من المصدر. هذه العقد يجب أن تبقى مسافتها ∞ أو ما يعادلها، ولا ينبغي محاولة تفسيرها كمسافات فعلية.
إذا تجنبت هذه الأخطاء، فأنت بالفعل تفهم الخوارزمية بشكل جيد.
كيف نقرأ النتيجة النهائية؟
بعد تشغيل Dijkstra، ستحصل عادة على جدول مسافات. هذا الجدول يخبرك بأقل كلفة من المصدر إلى كل عقدة. لكن ماذا يعني ذلك عمليًا؟ إذا كانت المسافة إلى عقدة معينة تساوي 0، فهذا يعني أنك في نقطة البداية. وإذا كانت 7، فهذا يعني أن أقل تكلفة للوصول إليها من المصدر تساوي 7. أما إذا كانت Infinity أو ∞، فهذا يعني أنه لا يوجد مسار يمكن الوصول به منها من المصدر في الرسم الحالي.
في التطبيقات العملية، هذه النتيجة قد تُعرض للمستخدم على هيئة:
أقل وقت للوصول.
أقل مسافة.
أقل تكلفة.
أقل عدد من المحطات.
أفضل مسار مقترح.
الجميل أن الخوارزمية لا تفرض معنى التكلفة، بل تتركه لك. أنت فقط تحتاج إلى أن تكون القيمة تمثل شيئًا يمكن جمعه ومقارنته، وأن تكون غير سالبة.
مثال تطبيقي على شبكة مدن
لنأخذ سيناريو أكثر واقعية. لديك مجموعة مدن متصلة بطرق، وكل طريق له طول بالكيلومترات. تريد معرفة أقصر طريق من مدينة معينة إلى باقي المدن. هنا تكون كل مدينة عقدة، وكل طريق حافة، وطول الطريق هو الوزن.
إذا أردت مثلًا معرفة أفضل طريق من الدار البيضاء إلى مدن أخرى، فيمكن تمثيل المدن كعقد، والطرق كحواف. ثم تنطلق الخوارزمية من مدينة البداية وتستكشف تدريجيًا أقصر المسافات. النتيجة يمكن أن تُستخدم مباشرة في نظام ملاحة أو تطبيق سفر أو تحليل لوجستي.
السبب الذي يجعل Dijkstra مناسبة هنا هو أن الطرق لا تحمل أوزانًا سالبة. لا يوجد “طريق يقلل المسافة” إلى أقل من الصفر. لذلك فإن فرضية الخوارزمية سليمة تمامًا.
لماذا تعتبر من الخوارزميات الأساسية؟
هناك خوارزميات تشعر وكأنها “فكرة أكاديمية”، وهناك خوارزميات تشعر وكأنك ستراها في كل مكان. Dijkstra من النوع الثاني. السبب أنها تدرّبك على عدة مفاهيم جوهرية في الوقت نفسه:
فهم الرسوم البيانية.
التفكير الجشع.
استخدام priority queue.
تحديث المسافات.
استرجاع المسار.
التمييز بين المسافة النهائية والتقدير المؤقت.
لهذا السبب، حتى لو لم تعمل يوميًا في مجال الرسوم البيانية، فإن تعلم Dijkstra يعطيك أساسًا قويًا جدًا في التفكير الخوارزمي.
نسخة شبه كود (Pseudo-code)
قد يكون من المفيد رؤية الخوارزمية في صورة شبه كود قبل أو بعد التطبيقات البرمجية:
Dijkstra(Graph, source):
create distance map
create previous map
for each vertex v in Graph:
distance[v] = infinity
previous[v] = null
distance[source] = 0
create min-priority-queue pq
pq.push((0, source))
while pq is not empty:
(dist, u) = pq.pop()
if dist > distance[u]:
continue
for each neighbor v of u with weight w:
alt = dist + w
if alt < distance[v]:
distance[v] = alt
previous[v] = u
pq.push((alt, v))
return distance, previous
هذا الوصف يلتقط جوهر الخوارزمية بدون تفاصيل لغة معينة. إذا فهمته جيدًا، سيكون من السهل عليك تحويله إلى Python أو JavaScript أو Java أو C++ أو أي لغة أخرى.
تطبيق Dijkstra في C++ بشكل مختصر
رغم أننا ركزنا على Python وJavaScript، من المفيد جدًا رؤية نسخة C++ أيضًا، لأنها شائعة في مسابقات البرمجة:
#include <bits/stdc++.h>
using namespace std;
vector<long long> dijkstra(int n, vector<vector<pair<int,int>>> &graph, int start) {
const long long INF = 1e18;
vector<long long> dist(n, INF);
dist[start] = 0;
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto &[v, w] : graph[u]) {
long long nd = d + w;
if (nd < dist[v]) {
dist[v] = nd;
pq.push({nd, v});
}
}
}
return dist;
}
هذا المثال قد يكون مألوفًا لمن يعمل على منصات مثل Codeforces وLeetCode. والأهم فيه هو استخدام greater<pair<long long,int>> لتحويل priority_queue إلى min-heap.
تحسينات إضافية يمكن التفكير فيها
في بعض البيئات، قد تحتاج إلى تحسينات خاصة. مثلًا، إذا كان لديك رسم ضخم جدًا وتريد تشغيل Dijkstra مرات كثيرة من مصادر مختلفة، فقد تفكر في:
تحسين تمثيل الرسم.
تقليل عمليات الإدخال والإخراج.
استخدام هياكل بيانات متخصصة.
تخزين نتائج جزئية إذا كانت المسألة تسمح بذلك.
أو حتى استخدام خوارزميات أخرى إذا كان هناك شرط إضافي على المشكلة.
في بعض المسائل، لا يكفي إيجاد أقصر طريق من مصدر واحد إلى كل العقد، بل قد تحتاج إلى أقصر طريق بين كل زوج من العقد. في هذه الحالة قد لا تكون Dijkstra وحدها الحل الأمثل، وقد تفكر في Floyd-Warshall إذا كان حجم الرسم صغيرًا نسبيًا، أو في تشغيل Dijkstra من مصادر متعددة وفق الحاجة.
متى تكون Dijkstra خيارًا ممتازًا؟
Dijkstra ممتازة عندما:
تكون الأوزان غير سالبة.
تريد أقصر مسار من مصدر واحد.
الرسم كبير نسبيًا لكن الحواف ليست كثيفة جدًا.
تحتاج إلى أداء جيد مع قابلية تنفيذ واضحة.
تريد استرجاع المسار الكامل وليس فقط المسافة.
بمعنى آخر، إذا كانت شروطها مناسبة، فغالبًا ستكون من أفضل الخيارات المتاحة.
فهمها كمبدأ ذهني
أحيانًا أفضل طريقة لفهم الخوارزمية ليست عبر الكود، بل عبر الصورة الذهنية. Dijkstra تقول لك: لا تحاول حل كل شيء مرة واحدة. ابدأ من المكان الذي تعرفه يقينًا، ثم وسّع معرفتك تدريجيًا إلى أقرب نقطة جديدة، وكرر العملية. لا تثق إلا في أفضل مسافة معروفة حاليًا، ثم حسّنها عندما تجد دليلاً أفضل. ومع كل خطوة، حافظ على سجل الطريق الذي وصلت منه.
هذا النمط من التفكير لا يفيد فقط في الخوارزميات، بل في حل المشكلات عمومًا. كثير من المشروعات البرمجية الكبيرة تُبنى بنفس الروح: ابدأ من الحالة المؤكدة، وسّع تدريجيًا، حدّث البيانات، ولا تفترض أكثر مما ينبغي. لهذا السبب يشعر الكثيرون أن Dijkstra ليست مجرد خوارزمية، بل درس في التنظيم والصبر والدقة.
أسئلة تدريبية تساعدك على الفهم
إذا أردت التأكد من أنك فهمت الخوارزمية فعلًا، فحاول أن تجيب عن هذه الأفكار بنفسك:
لماذا لا تعمل Dijkstra مع الأوزان السالبة؟
لماذا نحتاج priority queue؟
كيف نستخرج المسار نفسه؟
ما الفرق بينها وبين BFS؟
ما الذي يجعل العقدة المختارة نهائية؟
ماذا يحدث إذا كانت عقدة غير قابلة للوصول؟
كيف يتغير الأداء إذا استخدمت مصفوفة بدل heap؟
إذا استطعت الإجابة عن هذه الأسئلة بوضوح، فأنت لم تحفظ الخوارزمية فقط، بل فهمتها.
ملخص الفكرة في سطرين
خوارزمية Dijkstra تبحث عن أقصر مسار من عقدة مصدر إلى باقي العقد في رسم بياني ذي أوزان غير سالبة، عبر اختيار العقدة الأقرب غير المثبتة وتحديث جيرانها تدريجيًا. قوتها تأتي من بساطة منطقها، وسرعتها تأتي من استخدام بنية بيانات مناسبة مثل priority queue.
خاتمة
ربما تبدو Dijkstra في البداية مجرد اسم آخر في قائمة طويلة من الخوارزميات، لكن كلما تعمقت فيها ستشعر أنها واحدة من تلك الأفكار التي تستحق أن تتوقف عندها. هي بسيطة بما يكفي لتُفهم، وعميقة بما يكفي لتُستخدم، وأنيقة بما يكفي لتبقى في الذاكرة. وعندما تتقنها، ستجد أن كثيرًا من المسائل التي كانت تبدو مربكة بدأت تتخذ شكلًا أوضح. ستتعلم كيف تفكر في الطريق الأقل كلفة، وكيف تحوّل المشكلات الواقعية إلى رسوم بيانية، وكيف تبني حلًا تدريجيًا يراكم المعرفة دون أن يضيع في الاحتمالات.
إذا كنت تتعلم الخوارزميات للمرة الأولى، فاجعل Dijkstra من أولى محطاتك. وإذا كنت متمرسًا، فارجع إليها من حين لآخر، لأن جمالها الحقيقي ليس في الكود فقط، بل في الطريقة التي تعلّمك بها كيف تنظر إلى المشكلات. إنها خوارزمية تُثبت أن الحل الذكي ليس دائمًا هو الحل المعقد، وأن الاختيار الصحيح في الوقت الصحيح قد يختصر طريقًا طويلًا جدًا.
إضافة عملية: نسخة كاملة أكثر قربًا من الإنتاج في Python مع استرجاع المسار
import heapq
from typing import Dict, List, Tuple, Any
Node = Any
Graph = Dict[Node, List[Tuple[Node, int]]]
def dijkstra(graph: Graph, start: Node):
distances = {node: float("inf") for node in graph}
previous = {node: None for node in graph}
distances[start] = 0
heap = [(0, start)]
while heap:
current_distance, current_node = heapq.heappop(heap)
if current_distance != distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
new_distance = current_distance + weight
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
previous[neighbor] = current_node
heapq.heappush(heap, (new_distance, neighbor))
return distances, previous
def build_path(previous, start, end):
path = []
current = end
while current is not None:
path.append(current)
if current == start:
break
current = previous[current]
if not path or path[-1] != start:
return []
return list(reversed(path))
graph = {
"A": [("B", 4), ("C", 2)],
"B": [("C", 1), ("D", 5)],
"C": [("D", 8), ("E", 10)],
"D": [("E", 2)],
"E": []
}
distances, previous = dijkstra(graph, "A")
print("Distances:", distances)
print("Shortest path A -> E:", build_path(previous, "A", "E"))
هذا الشكل مناسب جدًا إذا أردت استخدام الخوارزمية داخل مشروع فعلي أو داخل درس تطبيقي. وقد تلاحظ هنا أننا استخدمنا مقارنة current_distance != distances[current_node] بدل المقارنة > فقط، وكلاهما شائع، لكن هذا الأسلوب شائع أيضًا لتجاهل الحالات القديمة الموجودة في heap.
إضافة عملية: مثال تعليمي يوضح التحديثات خطوة بخطوة
graph = {
"S": [("A", 1), ("B", 4)],
"A": [("B", 2), ("C", 5)],
"B": [("C", 1)],
"C": []
}
distances, previous = dijkstra(graph, "S")
print(distances)
print(build_path(previous, "S", "C"))
في هذا المثال، الطريق إلى C قد يمر عبر S -> A -> B -> C، وهو أفضل من S -> A -> C أو S -> B -> C. هذا يوضح أن المسار الأقصر ليس بالضرورة الأقصر في عدد الحواف، بل الأقصر في مجموع الأوزان.
كلمة أخيرة
في كل مرة تتعامل فيها مع شبكة، أو طريق، أو تكلفة، أو قرار له بدائل متعددة، تذكّر أن Dijkstra قد تكون واحدة من أول الأدوات التي ينبغي أن تفكر فيها. ليست مجرد خوارزمية “لأقصر مسار”، بل طريقة ناضجة ومنظمة للتعامل مع العالم حين يتحول إلى عقد وروابط وأثمان. وإذا كان هدفك أن تصبح أقوى في الخوارزميات أو في البرمجة عمومًا، فإتقانها خطوة مهمة جدًا ستفيدك كثيرًا على المدى الطويل.