Algorytm Floyda-Warshalla
Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.
Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.
Działanie algorytmu
Tworzymy dwie macierze o wymiarach n na n. W pierwszej macierzy będziemy przechowywać odległości między punktami, w drugiej identyfikatory przedostatnich punktów na ścieżce łączącej punkty. Bardziej formalnie, wartość di,j oznacza odległość z punktu i do punktu j, a wartość pi,j oznacza punkt poprzedzający punkt j na ścieżce z punktu i do punktu j.
Na początku inicjujemy wartości w macierzach. Jeśli istnieje krawędź prowadząca z punktu i do punktu j, to wartości di,j przypisujemy długość tej krawędzi, a wartość pi,j ustawiamy na i. W przeciwnym razie wartości di,j przypisujemy nieskończoność, a wartość pi,j traktujemy jako niezdefiniowaną. Długości ścieżek prowadzących do tego samego punktu, z którego wychodzą, ustawiamy na 0.
Następnie wykonujemy zasadniczą część algorytmu:
- Dla każdego punktu u ze zbioru wierzchołków:
- Dla każdego punktu v1 ze zbioru wierzchołków:
- Dla każdego punktu v2 ze zbioru wierzchołków:
- Jeśli dv1, v2 > dv1, u + du, v2, to:
- dv1, v2 = dv1, u + du, v2,
- pv1, v2 = pu, v2.
Po wykonaniu algorytmu macierze zawierają optymalne rozwiązania. Ścieżkę między dwoma dowolnymi punktami można odczytać wykorzystując wartości znajdujące się w macierzy p. Jeśli po wykonaniu algorytmu wartość di,j nadal wynosi nieskończoność, to oznacza, że nie istnieje żadna ścieżka prowadząca z punktu i do punktu j.
Jeśli po wykonaniu algorytmu na głównej przekątnej macierzy odległości znajduje się wartość mniejsza od zera, to graf zawiera ujemny cykl.
Złożoność obliczeniowa
Algorytm zawiera trzy zagnieżdżone pętle, w każdej z nich przeglądane są wszystkie wierzchołki. Złożoność czasowa algorytmu wynosi zatem O(n3) (n jest liczbą wierzchołków). Dane są przechowywane w dwóch macierzach o wymiarach n na n. Złożoność pamięciowa algorytmu wynosi zatem O(n2).
Liczba głosów: 6.
- Algorytm Bellmana-Forda
- Algorytm Dijkstry
- Algorytm Floyda-Warshalla
- Algorytm Johnsona
Dodano: 9 sierpnia 2017 13:51, ostatnia edycja: 10 sierpnia 2017 15:02.
Zobacz też
Metoda Forda-Fulkersona – algorytm służący do wyznaczania maksymalnego przepływu. Jest to algorytm bardzo ogólny, dlatego często nie jest nazywany algorytmem, a metodą. Popularną implementacją tej metody jest algorytm Edmondsa-Karpa. Algorytm można opisać następująco:
- Wyznacz sieć residualną (opis sieci residualnej znajduje się w dalszej części artykułu).
- Znajdź w sieci residualnej dowolną ścieżkę powiększającą.
- Jeśli nie udało się wyznaczyć żadnej ścieżki powiększającej, zakończ działanie algorytmu.
- W przeciwnym razie zwiększ przepływ w sieci (w sposób opisany w dalszej części artukułu) i wróć do punktu 1.
Algorytm Zhanga-Suena – algorytm służący do szkieletyzacji obrazu binarnego. Szkieletyzacja polega na wyborze z obrazu binarnego tych pikseli, które są równo odległe od krawędzi obiektu.
Rekurencja (inaczej rekursja) – odwołanie się funkcji lub definicji do samej siebie. Mówiąc inaczej, podejście rekurencyjne polega na tym, że rozwiązanie problemu wyraża się za pomocą rozwiązania tego samego problemu dla mniejszych danych wejściowych. Stosowanie rekurencji jest charakterystyczne dla algorytmów projektowanych metodą dziel i zwyciężaj.
Typowym problemem, dla którego można zastosować rekurencję, jest obliczanie silni. Przypomnijmy, że silnia z n jest zdefiniowana jako n!=1×2×…×n. Funkcja ta może być równoważnie zapisana jako:
n!=(n−1)!×n, dla n>0,
n!=1, dla n=0.
W powyższym przykładzie górny wiersz jest ogólnym równaniem rekurencji, zaś dolny wiersz jest wartością brzegową. W języku C++ powyższa funkcja byłaby zapisana w poniższy sposób.
int silnia(int n)
{
if (n > 0)
{
return n * silnia(n-1);
}
else
{
return 1;
}
};
Przekształcenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, która nie zawiera odwołania do samej siebie) jest określane jako rozwiązanie rekurencji. Metody rozwiązywania rekurencji są dostępne między innymi w książkach podanych w bibliografii.
Algorytmy stosujące rekurencję są zazwyczaj proste w implementacji. Jednocześnie wiążą się one z pewnymi problemami. Przy podejściu rekurencyjnym ta sama funkcja jest wywoływana wielokrotnie, co zużywa pamięć operacyjną (w skrajnych przypadkach może to spowodować przepełnienie stosu).