Floyd-Warshall: أقصر المسارات بين جميع الأزواج
املأ مصفوفة المسافات بين جميع الأزواج باستخدام خوارزمية Floyd-Warshall ذات الحلقات الثلاث المتداخلة، وطبّقها للعثور على أقل عدد من القفزات بين كل زوج من العقد.
Floyd-Warshall: أقصر المسارات بين جميع الأزواج درس مجاني في DSA Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في DSA Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
أقصر المسارات بين جميع الأزواج
تحسب Floyd-Warshall أقصر المسارات بين كل زوج من العقد في رسم بياني موزون، بما في ذلك الرسوم البيانية التي تحتوي على حواف ذات أوزان سالبة، ولكن ليس الدورات السالبة. يستغرق تشغيل Dijkstra من كل مصدر O(V × (V+E) log V)، بينما تعمل Floyd-Warshall في O(V³) بغض النظر عن كثافة الحواف. في الرسوم البيانية الكثيفة التي تحقق V ≤ 500، تكون Floyd-Warshall غالبًا أبسط وسرعتها مماثلة.
الفكرة الأساسية: العقد الوسيطة
تتمثل فكرة Floyd-Warshall في أن dp[i][j][k] تساوي أقصر مسار من i إلى j باستخدام العقد {0, 1, ..., k} فقط بوصفها عقدًا وسيطة. فإما أن يستخدم أقصر مسار العقدة k كعقدة وسيطة، أو لا يستخدمها. إذا استخدمها، فـ dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. وإذا لم يستخدمها، فـ dp[i][j][k] = dp[i][j][k-1]. وبما أن البعد الثالث يتقدم إلى الأمام فقط، يمكن حذفه، ولذلك نحدّث القيم في مكانها.
تهيئة مصفوفة المسافات
ابدؤوا بمصفوفة V×V: اجعلوا dist[i][i] = 0 (مسافة ذاتية تساوي صفرًا)، وdist[i][j] = weight للحواف المباشرة، وdist[i][j] = inf لعدم وجود الحواف. ثم كرروا على جميع العقد الوسيطة k، مع تحديث الأزواج (i, j). يجب أن تأتي الحلقة الخارجية التي تتكرر على k أولًا، حتى نبني المسارات بصورة صحيحة عبر مجموعة متزايدة من العقد الوسيطة المسموح بها.
def floyd_warshall(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w # directed graph
for k in range(V): # intermediate node
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return distتنفيذ كامل مع مثال
لنتتبّع خوارزمية Floyd-Warshall على رسم بياني مكوّن من 4 عقد. بعد معالجة كل عقدة وسيطة k، تمتلئ المصفوفة بمسارات أقصر تمر عبر العقدة k. تتعامل الخوارزمية طبيعيًا مع الانتقالات المتعددة من خلال بناء أقصر المسارات تدريجيًا.
def floyd_warshall(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] != INF and dist[k][j] != INF:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
V = 4
edges = [(0,1,3),(0,2,7),(1,2,1),(1,3,5),(2,3,2)]
dist = floyd_warshall(V, edges)
for row in dist:
print([x if x != float('inf') else 'INF' for x in row])اكتشاف الدورات السالبة
بعد تشغيل Floyd-Warshall، تحققوا من القطر الرئيسي: إذا كانت أي قيمة dist[i][i] < 0، فهناك دورة سالبة تمر عبر العقدة i. ويعود ذلك إلى أن الدورة السالبة تتيح الوصول من i إلى i بتكلفة سالبة. وإذا لم توجد دورة سالبة، فستظل جميع قيم القطر تساوي 0.
def has_negative_cycle_fw(V, edges):
dist = floyd_warshall(V, edges)
for i in range(V):
if dist[i][i] < 0:
return True # negative cycle through node i
return False
# Negative cycle: 0->1->2->0 with weights 1,-3,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-3),(2,0,1)]
print(has_negative_cycle_fw(3, edges_neg)) # Trueإعادة بناء المسار
لإعادة بناء المسار الفعلي من i إلى j، احتفظوا بمصفوفة next[i][j]: هيّئوا في البداية next[i][j] = j للحواف المباشرة. عند التحديث عبر العقدة الوسيطة k، عيّنوا next[i][j] = next[i][k]. ولاستعادة المسار، ابدأوا عند i واتبعوا مؤشرات next حتى الوصول إلى j. يضيف ذلك مساحة O(V²) وتعقيدًا قدره O(V) لإعادة بناء كل مسار.
def fw_with_path(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
nxt = [[None]*V for _ in range(V)]
for i in range(V): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w; nxt[u][v] = v
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
nxt[i][j] = nxt[i][k]
return dist, nxt
def get_path(nxt, i, j):
if nxt[i][j] is None: return []
path = [i]
while i != j:
i = nxt[i][j]; path.append(i)
return pathالإغلاق الانتقالي
هناك نسخة أبسط تُعرف باسم الإغلاق الانتقالي، وتجيب عن السؤال «هل يمكن الوصول إلى العقدة j من العقدة i؟» لجميع الأزواج. استبدلوا المسافات بقيم منطقية: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). هذه هي Floyd-Warshall باستخدام OR المنطقي بدلًا من الجمع وmin. هيّئوا reach[i][i] = True وreach[i][j] = True للحواف المباشرة.
def transitive_closure(V, edges):
reach = [[False]*V for _ in range(V)]
for i in range(V):
reach[i][i] = True
for u, v, _ in edges:
reach[u][v] = True
for k in range(V):
for i in range(V):
for j in range(V):
reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
return reach
edges = [(0,1,1),(1,2,1)]
R = transitive_closure(3, edges)
print(R[0][2]) # True (0 can reach 2 via 0->1->2)التعقيد ومتى تُستخدم
Floyd-Warshall: زمن O(V³) ومساحة O(V²). في الرسوم البيانية الكثيفة (E ≈ V²) التي تحقق V ≤ 300، تكون أسرع من تشغيل Dijkstra عدد V من المرات، إذ يكون تعقيدها أيضًا O(V³) في هذه الحالة. أما في رسم بياني قليل الكثافة حيث V = 1000 وE = 3000، فتبلغ تكلفة تشغيل Dijkstra عدد V من المرات O(V×E×log V) ≈ 33M، بينما تبلغ تكلفة Floyd-Warshall O(V³) = 10⁹، ولذلك تتفوق Dijkstra. اعرفوا متى يكون استخدام كل خوارزمية مناسبًا.
الحد الأدنى لعدد القفزات بين جميع الأزواج
اضبط أوزان جميع الحواف على 1 (أو استخدم مصفوفة تجاور منطقية مع Floyd-Warshall، مستخدماً الجمع بدلاً من min): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). يحسب هذا الحد الأدنى لعدد القفزات بين جميع الأزواج — أي نتيجة BFS بين جميع الأزواج، ولكن من خلال تمريرة واحدة من Floyd-Warshall بتعقيد O(V³).
def min_hops_all_pairs(V, adj_list):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for j in adj_list[i]:
dist[i][j] = 1
for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
adj = [[1,2],[2],[3],[],[]]
print(min_hops_all_pairs(5, adj)[0]) # [0, 1, 1, 2, INF]سياق المقابلات: متى يسأل المحاورون عن Floyd-Warshall
تظهر خوارزمية Floyd-Warshall في المقابلات ضمن أسئلة تتعلق بما يلي: (1) حساب المسافات بين جميع الأزواج في رسم بياني صغير، (2) التحقق من وجود أي دورة ذات وزن إجمالي سالب، (3) حساب أقصر المسارات في مسائل نشر القيود، و(4) المسائل التي تطلب صراحةً حلولاً بتعقيد O(V³) حيث V ≤ 200. احرص دائماً على ذكر بنية الحلقات الثلاث وضرورة عدم وجود دورات سالبة لضمان صحة النتيجة.
الرسوم البيانية غير الموجهة مع Floyd-Warshall
بالنسبة إلى الرسوم البيانية غير الموجهة، أضف الاتجاهين لكل حافة: dist[u][v] = dist[v][u] = weight. وتبقى بقية الخوارزمية كما هي. تكون المصفوفة الناتجة متماثلة: dist[i][j] == dist[j][i] لجميع الأزواج. عند التهيئة، انتبه إلى عدم إسناد حواف موجهة عن طريق الخطأ — إذ يجب إضافة الحواف غير الموجهة في الاتجاهين إلى المصفوفة الأولية قبل تشغيل الحلقات الثلاث.
def fw_undirected(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
dist[v][u] = w # both directions for undirected
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return distتحقق سريع
اختبر مدى فهمك لمفاهيم هياكل البيانات والخوارزميات — الاستعداد لمقابلات البرمجة — التي تناولها هذا الدرس.
مراجعة الدرس
تعلمت في هذا الدرس أن: Floyd-Warshall تحسب أقصر المسارات بين جميع الأزواج باستخدام ثلاث حلقات متداخلة والعلاقة التكرارية dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])، وأن الدورات السالبة يمكن اكتشافها بالتحقق مما إذا كانت أي قيمة dist[i][i] < 0 بعد اكتمال التنفيذ، وأن الخوارزمية تعمل بزمن O(V³) ومساحة O(V²). سنتناول تالياً تطبيقات أقصر المسارات مجدداً، مع Network Delay Time وتقنيات إعادة بناء المسار.
الأسئلة الشائعة
هل درس «Floyd-Warshall: أقصر المسارات بين جميع الأزواج» مجاني؟
نعم — نص درس «Floyd-Warshall: أقصر المسارات بين جميع الأزواج» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة DSA Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «Floyd-Warshall: أقصر المسارات بين جميع الأزواج»؟
املأ مصفوفة المسافات بين جميع الأزواج باستخدام خوارزمية Floyd-Warshall ذات الحلقات الثلاث المتداخلة، وطبّقها للعثور على أقل عدد من القفزات بين كل زوج من العقد. تتمرن على DSA Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ DSA Interview Prep؟
لا تُشترط خبرة سابقة. DSA Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «Floyd-Warshall: أقصر المسارات بين جميع الأزواج»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس DSA Interview Prep هذا؟
نعم. كل درس في DSA Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- خوارزمية Dijkstra مع طابور أولوية
- Bellman-Ford والدورات سالبة الوزن
- Floyd-Warshall: أقصر المسارات بين جميع الأزواج
- زمن تأخير الشبكة وإعادة بناء المسار