سؤال: هل ممكن نتفوّق على 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 ببايثون) ولا
أصبحت أداة هندسية يومية.
جدول سريع
| الخوارزمية | سنة النشر | التعقيد (رسم موجّه) | الاستخدام |
|---|---|---|---|
| Dijkstra (بـ Heap) | 1959 | O(m + n log n) | معياري، مستخدَم بكل مكان |
| خوارزمية Duan وفريقه | 2025 | O(m log^(2/3) n) | نتيجة نظرية بحثية، أول كسر لحاجز الفرز |
أخطاء شائعة (تصورات خاطئة)
- الاعتقاد أن Dijkstra "الأمثل نظريًا للأبد" — كان صحيحًا فقط ضمن حدود نموذج معيّن، وثبت أنه ليس الأمثل المطلق بهذا النموذج بعد 2025.
- الخلط بين "أسرع نظريًا" (asymptotically) و"أسرع عمليًا" — خوارزميات نظرية أسرع غالبًا لها ثوابت وتعقيد تنفيذ كبيرة تجعلها أبطأ فعليًا على أحجام بيانات عادية.
- الاعتقاد أن هذا يبطّل درس Dijkstra — لا، لسا الأساس اللي تحتاجه بأي مقابلة أو مشروع حقيقي.
💡 الدرس الأهم هون مو الخوارزمية نفسها، بل إنه حتى "الحقائق المستقرة" بعلوم الحاسوب اللي صمدت لعقود ممكن تنكسر — المجال لسا حي وبيتطوّر.
🎯 التالي: Union-Find — هيكل بيانات لتتبّع المجموعات المنفصلة، أساس خوارزمية Kruskal لإيجاد الشجرة الممتدة الصغرى.