Jako, że szanse napisania tego artykułu przez jego pierwotnego autora właśnie zniknęły(jeśli kiedykolwiek były) to ja go napiszę :)
Algorytm Floyda-Warshalla
Algorytm Floyda-Warshalla służy do wyznaczania najkrótszych ścieżek między wszystkimi parami wierzchołków w grafie. Graf ten może być ważony(dodatnimi/ujemnymi wagami)/jednostkowy, skierowany/nieskierowany, spójny/niespójny, multigraf/niemultigraf => dowolny.
Wyznacza on macierz rozmiaru n x n gdzie pozycja w i-tej kolumnie i j-tym wierszu wynosi długość najkrótszej ścieżki między wierzchołkiem i-tym, a j-tym (jeśli taka ścieżka nie istnieje to jest tam nieskończoność).
Jest to algorytm dynamiczny: w każdym obiegu pierwszej petli dodajemy kolejny wierzchołek, przez który mogą prowadzić najkrótsze ścieżki. Po zakończeniu mamy rozważone najkrótsze ścieżki uwzględniające wszystkie wierzchołki, czyli ogólnie najkrótsze ścieżki w grafie.
Przed uruchomieniem Floyda mamy najkrótsze ścieżki, które nie przechodzą przez żaden wierzchołek (prócz pierwszego i docelowego). Czyli ściezki, które są krawędziami.
F[u][v] = w(u,v) jeśli (u,v) należy do E
0 jeśli u = v
INF jeśli (u,v) nie należy do E
Następnie rozważamy najkrótsze ściezki przechodzące przez kolejne wierzchołki:
for k = 1 to |V|
for i = 1 to |V|
for j = 1 to |V|
F[i][j] = min(F[i][j], F[i][k] + F[k][j])
W tym momencie macierz F zawiera wartości najkrótszych ścieżek między każdą parą wierzchołków. Koniec algorytmu.
Złożoność czasowa: $O(V^3)$ (trzy zagnieżdżone pętle wykonujące się V-krotnie)
Złożoność pamięciowa: $O(V^2)$ (macierz)
Domknięcie przechodnie
Mając daną relacje $f$, która jest dwuargumentowa oraz przechodnia można wyznaczyć jej domknięcie przechodnie.
Co to jest? (na przykładzie)
Weźmy relację mniejszości na liczbach rzeczywistych. Jest ona dwuargumentowa(porównujemy dwie liczby) oraz przechodnia(jeśli a < b i b < c to a < c).
Mając dany zbiór liczb np $A = \{3,5,7,9\}$ oraz wiedząc, że 3 < 5 i 5 < 7 i 5 < 9 domknięcie przechodnie to zbiór wszystkich takich par liczb, że pierwsza jest mniejsza od drugiej i można to wywnioskować korzystając z przechodności oraz pierwszych danych relacji (w tym przykładzie nie da się wywnioskować czy 7 < 9 czy nie).
Przykład w teorii grafów
Mając daną macierz sąsiedztwa domknięcie przechodnie to będzie osiągalność między każdą parą wierzchołków (czyli czy z wierzchołka v istnieje jakaś ścieżka do wierzchołka u).
Domknięcie przechodnie można wyznaczyć algorytmem Floyda-Warshalla.
Na początku ustawiamy relacje, które znamy.
F[i][j] = 1 jeśli zachodzi relacja (i,j)
0 jeśli nie
A następnie odpalamy Floyda.
for k = 1 to n
for i = 1 to n
for j = 1 to n
F[i][j] |= (F[i][k] && F[k][j])
Koniec.
