Floyd-Warshall

Graflar O(V³) O(V²)

Dinamik programlamayla tüm-çiftler en kısa yol: k turu her çifte, k düğümünde mola vermenin yolu kısaltıp kısaltmadığını sorar.

i\j	0	1	2	3
0	0	3	∞	7
1	8	0	2	∞
2	5	∞	0	1
3	2	∞	∞	0

k0123k turu = izinli ara durak

1/41

Kenar matrisinden başlanıyor: dist[i][j] = doğrudan kenar (∞ = yok).

Değişmezdist[i][j], yalnızca k'dan küçük düğümlerde mola veren en kısa yoldur.

hesaplanıyorokuduğudolu

floyd-warshall.c

#define V 4
#define INF 1000000
 
void floydWarshall(int dist[V][V]) {
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k]
                               + dist[k][j];
            }
        }
    }
}

Floyd-Warshall nasıl çalışır?

Ara düğümler üzerinde dinamik programlama: k. turdan sonra dist[i][j], yalnızca 0..k düğümlerini durak olarak kullanan en kısa yoldur. k. tur her çifte tek soru sorar — k üzerinden gitmek daha mı kısa?

En kötü durum

Her zaman Θ(V³) — ama çok küçük sabitle ve veri yapısız.

Ne zaman kullanılır?

Küçük/yoğun graflarda tüm-çiftler en kısa yol; negatif kenarları da işler (negatif döngü yoksa).