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: 12.
- 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ż
Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.
Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).
Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.
Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.
Wyznaczanie najkrótszej ścieżki – zagadnienie polegające na wyszkaniu w grafie takiej ścieżki łączącej dwa wierzchołki, której suma wag krawędzi jest jak najmniejsza.
W przypadku pesymistycznym do wyznaczenia optymalnej ścieżki z wierzchołka A do wierzchołka B konieczne jest wyznaczenie najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych wierzchołków w grafie. Zagadnienie takie jest określane jako poszukiwanie najkrótszych ścieżek z jednego źródła. Do rozwiązywania tego zagadnienia można wykorzystać następujące algorytmy:
Nieco innym zagadnieniem jest poszukiwanie najkrótszych ścieżek pomiędzy każdą parą wierzchołków. W tym celu można wykorzystać algorytmy wymienione powyżej (wykonując je wielokrotnie, za każdym razem przyjmując inny wierzchołek źródłowy) lub algorytmy poszukujące od razu wszystkich ścieżek, takie jak:
Aby znalezienie najkrótszej ścieżki było możliwe, graf nie może zawierać ujemnych cykli osiągalnych z wierzchołka źródłowego. Jeśli taki cykl istnieje, to poruszając się nim „w kółko” cały czas zmniejszamy długość ścieżki. Dopuszczalne jest natomiast występowanie krawędzi o ujemnej wadze, choć nie wszystkie algorytmy dopuszczają ten przypadek.
Jeśli poszukujemy ścieżek o najmniejszej liczbie krawędzi (np. wtedy, gdy wszystkie krawędzie mają taką samą, dodatnią wagę), to zamiast powyższych algorytmów możemy skorzystać z prostego przeszukiwania grafu wszerz.