خوارزمية Dijkstra باستخدام كومة
أقصر المسارات الجشعة على حواف غير سالبة
خوارزمية Dijkstra باستخدام كومة درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
مشكلة أقصر مسار
تريد إيجاد المسار الأقل تكلفة من عقدة واحدة إلى كل عقدة أخرى. تحلّ خوارزمية Dijkstra هذه المشكلة عندما تكون أوزان جميع الحواف صفرًا أو موجبة.
الفكرة الجشعة
خوارزمية Dijkstra جشعة: فهي توسّع دائمًا العقدة التي لم تُزَر وتملك أصغر مسافة معروفة، وتفترض أن هذه المسافة نهائية.
لماذا نستخدم كومة الحد الأدنى
للحصول على أقرب عقدة بسرعة، تحتاج إلى كومة حد أدنى. فهي تمنحك أصغر مسافة في زمن log n بدلًا من إجراء مسح بطيء.
import heapqابدأ بالمسافات
عيّن قيمة اللانهاية لكل مسافة، ثم اجعل مسافة المصدر صفرًا. وتبقى العقد التي لم نصل إليها عند اللانهاية إلى الأبد.
dist = [float('inf')] * n
dist[src] = 0هيّئ الكومة
أضف المصدر إلى الكومة بوصفه tuple مكوّنًا من (distance, node). ويتيح وضع المسافة أولًا للكومة ترتيب العناصر تلقائيًا حسب التكلفة.
pq = [(0, src)]أخرج أقرب عقدة
في كل تكرار، نفّذ pop لأصغر عنصر (d, u). تمثل d أقصر مسافة إلى u، لذلك تنتهي معالجتها بمجرد إخراجها.
d, u = heapq.heappop(pq)تجاهل العناصر القديمة
قد تبقى عقدة في الكومة بمسافة قديمة وأكبر. نفّذ تجاهلًا لها عندما تكون d أسوأ من المسافة المخزنة.
if d > dist[u]:
continueأرخِ الحواف المجاورة
تعني عملية الإرخاء محاولة تحسين مسافة عقدة مجاورة: فإذا كان المرور عبر u أقل تكلفة، حدّث مسافتها وأضفها إلى الكومة.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))حيلة الحذف الكسول
لا تستطيع أكوام Python تحديث مفتاح، لذلك تضيف نسخًا مكررة وتتجاهل العناصر القديمة. ويحافظ هذا الأسلوب الكسول على قِصر الشيفرة وسرعتها.
زمن التنفيذ
باستخدام كومة ثنائية، تعمل خوارزمية Dijkstra في O((V + E) log V). وهذا يتعامل بسهولة مع الرسوم البيانية التي تحتوي على مئات الآلاف من الحواف.
انتبه إلى أوزان الحواف
تفشل خوارزمية Dijkstra مع الحواف السالبة، لأن المسافة التي أُخرجت قد لا تكون نهائية. استخدم Bellman-Ford بدلًا منها في هذه الحالة.
اختبار سريع
أخرجت (d, u)، لكن d أكبر من dist[u]. ماذا يجب أن تفعل؟
مراجعة: Dijkstra مع كومة
تهيّئ المسافات، وتضيف (dist, node)، وتخرج الأقرب، وتتجاهل العناصر القديمة، وترخي الحواف المجاورة. هذه هي خوارزمية Dijkstra في زمن O((V+E) log V). 🚀
الأسئلة الشائعة
هل درس «خوارزمية Dijkstra باستخدام كومة» مجاني؟
نعم — نص درس «خوارزمية Dijkstra باستخدام كومة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «خوارزمية Dijkstra باستخدام كومة»؟
أقصر المسارات الجشعة على حواف غير سالبة تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «خوارزمية Dijkstra باستخدام كومة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- خوارزمية Dijkstra باستخدام كومة
- 0-1 BFS باستخدام Deque
- Bellman-Ford والحواف السالبة
- Floyd-Warshall لجميع الأزواج