خوارزمية Dijkstra مع طابور أولوية
طبّق Dijkstra باستخدام heapq، وتتّبع خطوات إرخاء الحواف على رسم بياني موزون، وحلّ مسألة أرخص الرحلات الجوية خلال k من التوقفات.
خوارزمية Dijkstra مع طابور أولوية درس مجاني في DSA Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في DSA Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
أقصر مسار في الرسوم البيانية الموزونة
تجد خوارزمية Dijkstra أقصر مسار من عقدة مصدر واحدة إلى جميع العقد الأخرى في رسم بياني موزون ذي أوزان حواف غير سالبة. تعمل الخوارزمية على معالجة العقد جشعًا وفق مسافتها الحالية الأفضل المعروفة، فتوسّع دائمًا أقرب عقدة لم تُزر. وبنية البيانات الأساسية هي كومة دنيا (طابور أولوية) تسترجع بكفاءة العقدة ذات أصغر مسافة.
نظرة عامة على خطوات الخوارزمية
خوارزمية Dijkstra: (1) هيّئ dist[source] = 0 وdist[all others] = inf. (2) ادفع (0, source) إلى كومة دنيا. (3) أخرج العقدة u ذات أصغر مسافة. إذا كانت قد زِيرت مسبقًا بمسافة أصغر، فتخطّها. (4) لكل جار v للعقدة u: إذا كان dist[u] + weight(u,v) < dist[v]، فحدّث dist[v] وادفع (dist[v], v) إلى الكومة. (5) كرّر ذلك حتى تفرغ الكومة.
تطبيق Python باستخدام heapq
تنفّذ heapq في Python كومة دنيا. نمثّل الرسم البياني بقائمة تجاور: graph[u] = [(v, weight), ...]. وتخزّن الكومة صفوفًا من الشكل (distance, node). نستخدم مجموعة visited لتخطي الإدخالات القديمة في الكومة، أي الإدخالات التي أُضيفت قبل العثور على مسار أفضل.
import heapq
def dijkstra(graph, source):
n = len(graph)
dist = [float('inf')] * n
dist[source] = 0
heap = [(0, source)] # (distance, node)
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(heap, (dist[v], v))
return distمثال محلول
لنفترض رسمًا بيانيًا يحوي 5 عقد وحوافًا: 0→1 (4)، 0→2 (1)، 2→1 (2)، 1→3 (1)، 2→3 (5)، 3→4 (3). أقصر المسارات من العقدة 0 هي: إلى 1 عبر 0→2→1 بتكلفة 3، وإلى 2 بتكلفة 1، وإلى 3 عبر 0→2→1→3 بتكلفة 4، وإلى 4 عبر 0→2→1→3→4 بتكلفة 7. تجد خوارزمية Dijkstra جميع هذه المسارات في مرور واحد، وليس مسارًا واحدًا إلى هدف محدد فقط.
import heapq
def dijkstra(graph, source):
dist = [float('inf')] * len(graph)
dist[source] = 0
heap = [(0, source)]
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
graph = [
[(1,4),(2,1)], # 0
[(3,1)], # 1
[(1,2),(3,5)], # 2
[(4,3)], # 3
[] # 4
]
print(dijkstra(graph, 0)) # [0, 3, 1, 4, 7]لماذا تفشل خوارزمية Dijkstra مع الأوزان السالبة
تعتمد صحة خوارزمية Dijkstra على حقيقة أن مسافة العقدة تصبح نهائية بمجرد إخراجها من الكومة الدنيا. ولا يصح ذلك إلا إذا كانت أوزان الحواف غير سالبة. فعند وجود حافة سالبة u→v بوزن -5، قد نجد بعد زيارة v مسارًا يمر عبر u ويكون أقصر، لكن v تكون قد عُلّمت بالفعل على أنها مُزارة. ويمكن لحافة سالبة واحدة أن تُبطل جميع حسابات المسافات اللاحقة.
أرخص الرحلات الجوية ضمن K توقفات (LeetCode 787)
تضيف هذه المسألة قيدًا يتمثل في السماح بحد أقصى k من التوقفات. لا تتعامل خوارزمية Dijkstra القياسية مع عدد الخطوات بصورة أصلية. الحل هو توسيع الحالة لتصبح (cost, node, stops_remaining). استخدموا Dijkstra مع هذه الثلاثية، أو استخدموا Bellman-Ford مع k+1 من جولات الإرخاء. تتوقف نسخة Dijkstra المعدّلة عندما تصل قيمة stops_remaining إلى 0، مما يمنع الانتقالات الإضافية.
import heapq
from collections import defaultdict
def findCheapestPrice(n, flights, src, dst, k):
graph = defaultdict(list)
for u, v, w in flights:
graph[u].append((v, w))
heap = [(0, src, k + 1)] # (cost, node, hops_left)
visited = {} # node -> min hops_left seen at this cost level
while heap:
cost, node, hops = heapq.heappop(heap)
if node == dst:
return cost
if hops == 0:
continue
if visited.get(node, 0) >= hops:
continue
visited[node] = hops
for nxt, w in graph[node]:
heapq.heappush(heap, (cost + w, nxt, hops - 1))
return -1
print(findCheapestPrice(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)) # 200تحليل التعقيد الزمني
باستخدام كومة ثنائية، تعمل خوارزمية Dijkstra في زمن O((V + E) log V): إذ تُخرج كل رأس مرة واحدة (أي V عملية إخراج)، وقد تؤدي كل حافة إلى عملية إدراج (أي E عمليات إدراج)، وتستغرق كل عملية على الكومة O(log V). باستخدام كومة فيبوناتشي، يتحسن الحد إلى O(E + V log V)، لكن heapq في Python عبارة عن كومة ثنائية. في الرسوم البيانية قليلة الكثافة (E ≈ V)، تكون نسخة الكومة الثنائية O(V log V)، أما في الرسوم البيانية كثيفة الكثافة (E ≈ V²) فتكون O(V² log V).
إعادة بناء أقصر مسار
لاستعادة المسار الفعلي، وليس المسافات فقط، احتفظوا بمصفوفة prev: عند تحديث dist[v]، عيّنوا prev[v] = u. بعد اكتمال الخوارزمية، أعيدوا بناء المسار من المصدر إلى الوجهة بتتبّع المؤشرات إلى الخلف: ابدأوا عند dst، واتبعوا مؤشرات prev حتى الوصول إلى source، ثم اعكسوا النتيجة.
import heapq
def dijkstra_path(graph, source, target):
n = len(graph)
dist = [float('inf')] * n
prev = [-1] * n
dist[source] = 0
heap = [(0, source)]
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited: continue
visited.add(u)
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct
path, node = [], target
while node != -1:
path.append(node)
node = prev[node]
return dist[target], path[::-1]استخدام قاموس للرسوم البيانية قليلة الكثافة
عندما تكون العقد سلاسل نصية أو أعدادًا صحيحة غير متجاورة، استخدموا defaultdict(list) لقائمة التجاور، وdict عاديًا للمسافات. وهذا شائع في مسائل LeetCode مثل Network Delay Time، حيث تُرقّم العقد من 1 إلى n. تذكّروا استخدام dist = {node: inf for node in all_nodes} والتحقق من العقد التي يتعذر الوصول إليها بعد تنفيذ الخوارزمية.
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
dist[k] = 0
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2مقارنة مع BFS في الرسوم البيانية غير الموزونة
بالنسبة إلى الرسوم البيانية غير الموزونة، يجد BFS أقصر المسارات في O(V + E)، وهو أسرع من Dijkstra التي تعمل في O((V+E) log V). تعمّم Dijkstra خوارزمية BFS على الرسوم البيانية الموزونة، وذلك باستخدام طابور أولوية بدلًا من طابور FIFO عادي. عندما تكون جميع أوزان الحواف متساوية، تتحول Dijkstra عمليًا إلى BFS. اختاروا BFS للرسوم البيانية غير الموزونة، وDijkstra للأوزان غير السالبة، وBellman-Ford للأوزان السالبة.
خوارزمية Dijkstra مع تحسين تقليل المفتاح
تستخدم خوارزمية Dijkstra في الكتب التعليمية طابور أولوية مع decrease-key: فعندما تتحسن مسافة عقدة، تُحدَّث أولويتها في مكانها. يتطلب ذلك كومة فيبوناتشي للوصول إلى O(E + V log V)، لكنه صعب التنفيذ. أما أسلوب الحذف الكسول المستخدم في المقابلات، فيُدرج إدخالًا جديدًا ويتجاوز عمليات الإخراج القديمة، وهو أبسط ولا يضيف سوى تكلفة ثابتة. في Python، يُعد الحذف الكسول باستخدام heapq هو التنفيذ القياسي في مقابلات البرمجة.
تحقق سريع
اختبروا مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep الواردة في هذا الدرس.
مراجعة الدرس
تعلّمتم في هذا الدرس أن Dijkstra تستخدم كومة دنيا لمعالجة العقد جشعًا وفقًا لأفضل مسافة حالية، وأن زمن تنفيذها هو O((V+E) log V) وتفشل مع الحواف ذات الأوزان السالبة، وأن إدخالات الكومة القديمة تُعالج بالتحقق من مجموعة العقد المُزارة عند إخراجها. سنتناول بعد ذلك Bellman-Ford، التي تتعامل مع الأوزان السالبة من خلال n-1 من جولات الإرخاء.
الأسئلة الشائعة
هل درس «خوارزمية Dijkstra مع طابور أولوية» مجاني؟
نعم — نص درس «خوارزمية Dijkstra مع طابور أولوية» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة DSA Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «خوارزمية Dijkstra مع طابور أولوية»؟
طبّق Dijkstra باستخدام heapq، وتتّبع خطوات إرخاء الحواف على رسم بياني موزون، وحلّ مسألة أرخص الرحلات الجوية خلال k من التوقفات. تتمرن على DSA Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ DSA Interview Prep؟
لا تُشترط خبرة سابقة. DSA Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «خوارزمية Dijkstra مع طابور أولوية»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس DSA Interview Prep هذا؟
نعم. كل درس في DSA Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- خوارزمية Dijkstra مع طابور أولوية
- Bellman-Ford والدورات سالبة الوزن
- Floyd-Warshall: أقصر المسارات بين جميع الأزواج
- زمن تأخير الشبكة وإعادة بناء المسار