45. أقصر مسار لجميع الأزواج (All-Pairs Shortest Path): مقدمة إلى Floyd-Warshall

في بعض الأحيان، لا نحتاج فقط إلى أقصر مسار من مصدر واحد، بل إلى أقصر مسار بين كل زوج من الرؤوس. هذه هي مشكلة أقصر مسار لجميع الأزواج.

خوارزمية Floyd-Warshall

Floyd-Warshall هي خوارزمية كلاسيكية تستخدم البرمجة الديناميكية (Dynamic Programming) (سيتم تغطيتها قريباً) لحل هذه المشكلة بكفاءة.

المفهوم

تعتبر كل رأس محتمل k كعُقدة وسيطة للمسارات بين عُقدتين أخريين i و j.

لكل زوج من الرؤوس (i, j)، تتحقق مما إذا كان المرور عبر رأس وسيط k أقصر من أقصر مسار معروف حالياً.

python 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])

• التعقيد الزمني: O(V³). تكون فعالة عندما تكون V صغيرة نسبياً (مئات)، ولكنها أقل كفاءة للرسوم البيانية الضخمة.