سؤال: هل ممكن نتفوّق على Dijkstra؟
بدرس Dijkstra تعلّمت أن استخدام Priority Queue (كومة) يحسّن التعقيد إلى O((V+E) log V). لعقود طويلة، اعتقد أغلب الباحثين أن هذا هو الحد الأفضل الممكن ضمن "نموذج المقارنة" (comparison-addition model) — أي أن أي خوارزمية عامة لأقصر مسار (بدون معرفة مسبقة ببنية الرسم البياني) لازم تدفع ثمن فرز/ترتيب العقد بشكل أو بآخر، تمامًا متل ما الفرز نفسه محكوم بحد أدنى نظري O(n log n).
هذا الافتراض صمد من نشر Dijkstra خوارزميته عام 1959 حتى... 2025.
الاختراق: كسر "حاجز الفرز"
بأبريل 2025، نشر باحثون من جامعة تسينغهوا (بالتعاون مع باحث من ستانفورد) — Ran Duan وJiayi Mao وXiao Mao وXinkai Shu وLonghui Yin — ورقة بحثية بعنوان "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths"، قُدّمت لاحقًا بمؤتمر STOC 2025 (أحد أهم مؤتمرات نظرية علوم الحاسوب) وفازت بجائزة أفضل ورقة بحثية (Best Paper Award).
الخوارزمية الجديدة حتمية (deterministic، مو عشوائية) وتعمل بزمن O(m log^(2/3) n) على رسوم بيانية موجّهة بأوزان حقيقية غير سالبة — أول خوارزمية تتفوّق نظريًا على حد O(m + n log n) الخاص بـ Dijkstra بالرسوم البيانية النادرة (sparse graphs، حيث عدد الأضلاع قريب من عدد العقد).
كيف؟ الفكرة العامة (بدون تفاصيل رياضية معقّدة)
بدل الاعتماد الكلي على قائمة أولوية تفرز كل العقد المرشّحة قبل اختيار الأرخص، تدمج الخوارزمية الجديدة أسلوب "الاسترخاء" (Relaxation) من Bellman-Ford — الذي لا يحتاج فرزًا — مع تقسيم متكرر (recursive partitioning) للعقد إلى مجموعات أصغر، بدل الاحتفاظ بجبهة واحدة مرتّبة بالكامل بكل خطوة. هذا يتفادى كلفة الفرز الكامل التي كانت تُعتبر ثمنًا لا مفر منه.
هل يغيّر هذا كودك اليوم؟
عمليًا، لا. Dijkstra بـ Heap يبقى الخيار القياسي بأي مقابلة عمل أو مشروع
حقيقي — بسيط، مُختبر، ومكتبات كل لغة تدعمه جاهزًا. الخوارزمية الجديدة
معقّدة التنفيذ، وفائدتها النظرية تظهر بمقاييس كبيرة جدًا ورسوم بيانية
نادرة تحديدًا؛ لسا ما دخلت المكتبات القياسية (زي heapq ببايثون) ولا
أصبحت أداة هندسية يومية.
تحديث: تحسين إضافي (فبراير 2026)
اختراق 2025 مو "الكلمة الأخيرة" — البحث النظري استمر. بفبراير 2026، نشر Ran Duan وXiao Mao وXinkai Shu وLonghui Yin (نفس فريق 2025 تقريبًا) ورقة جديدة بعنوان "A Faster Directed Single-Source Shortest Path Algorithm"، مقبولة بمؤتمر ICALP 2026 (International Colloquium on Automata, Languages and Programming — مؤتمر رئيسي بنظرية علوم الحاسوب). النسخة الجديدة تحسّن التعقيد على الرسوم البيانية النادرة إلى O(m √(log n · log log n)) — أفضل (نظريًا) من O(m log^(2/3) n) بنسخة 2025 الأصلية.
هذا يؤكّد نفس الدرس: الحاجز النظري القديم انكسر فعلًا، والتحسين مستمر — لكن عمليًا، هذا لسا بحث نظري بحت، ما وصل لأي مكتبة قياسية ولا غيّر التوصية العملية (استخدم Dijkstra بـHeap بمشاريعك الحقيقية).
جدول سريع
| الخوارزمية | سنة النشر | التعقيد (رسم موجّه، نادر) | الاستخدام |
|---|---|---|---|
| Dijkstra (بـ Heap) | 1959 | O(m + n log n) | معياري، مستخدَم بكل مكان |
| خوارزمية Duan وفريقه | 2025 | O(m log^(2/3) n) | نتيجة نظرية بحثية، أول كسر لحاجز الفرز |
| تحسين Duan وفريقه (ICALP 2026) | 2026 | O(m √(log n · log log n)) | تحسين نظري إضافي على نسخة 2025 |
أخطاء شائعة (تصورات خاطئة)
- الاعتقاد أن Dijkstra "الأمثل نظريًا للأبد" — كان صحيحًا فقط ضمن حدود نموذج معيّن، وثبت أنه ليس الأمثل المطلق بهذا النموذج بعد 2025.
- الخلط بين "أسرع نظريًا" (asymptotically) و"أسرع عمليًا" — خوارزميات نظرية أسرع غالبًا لها ثوابت وتعقيد تنفيذ كبيرة تجعلها أبطأ فعليًا على أحجام بيانات عادية.
- الاعتقاد أن هذا يبطّل درس Dijkstra — لا، لسا الأساس اللي تحتاجه بأي مقابلة أو مشروع حقيقي.
- الاعتقاد أن نتيجة 2025 هي آخر تطوّر بهذا المجال — التحسين النظري مستمر (نسخة 2026 مثال حي)، وهذا طبيعي بأي مجال بحثي نشط.
💡 الدرس الأهم هون مو الخوارزمية نفسها، بل إنه حتى "الحقائق المستقرة" بعلوم الحاسوب اللي صمدت لعقود ممكن تنكسر — المجال لسا حي وبيتطوّر.
🎯 التالي: Union-Find — هيكل بيانات لتتبّع المجموعات المنفصلة، أساس خوارزمية Kruskal لإيجاد الشجرة الممتدة الصغرى.