خوارزمية Floyd-Warshall Floyd-Warshall Algorithm

الصياغة

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]

📄 مثال

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] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

edges = [(0, 1, 3), (1, 2, 1), (0, 2, 10)]
print(floyd_warshall(3, edges))  # [[0, 3, 4], [inf, 0, 1], [inf, inf, 0]]

أهم النقاط

💡 نصائح عملية

• استخدمها فقط عندما تحتاج فعلًا مسافات كل الأزواج على رسم صغير إلى متوسط الحجم؛ لرسم كبير جدًا شغّل Dijkstra من كل مصدر بدلًا منها

⚠️ أخطاء شائعة

• وضع حلقة k في غير الترتيب الخارجي — يكسر منطق البرمجة الديناميكية ويعطي نتائج خاطئة

خصائص ذات صلة