Algorytm Floyda-Warshalla

Tutorial
Na ten temat mamy również tutorial „Algorytm Floyda-Warshalla”, który ilustruje działanie algorytmu krok po kroku. Zapraszamy do zapoznania się z nim!
REKLAMA

Czysty kod. Podręcznik dobrego programisty
−35%51,35 zł
C++. Algorytmy i struktury danych
129,00 zł

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).

Ocena: +11 Tak Nie
Liczba głosów: 11.

Dodano: 9 sierpnia 2017 13:51, ostatnia edycja: 10 sierpnia 2017 15:02.

REKLAMA

Zobacz też

Graf – struktura G = (V, E) składająca się ze skończonego zbioru wierzchołków V oraz skończonego zbioru krawędzi E, gdzie każda krawędź e ∈ E jest dwuelementowym zbiorem wierzchołków u, v ∈ V. Wierzchołki u, v połączone krawędzią e = {u, v} określane są sąsiednimi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawiać rożnego rodzaju relacje pomiędzy obiektami.

Powyższa definicja dotyczy grafu nieskierowanego, gdzie relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.

Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.

→ Czytaj całość

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.

→ Czytaj całość

Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).

→ Czytaj całość
Polityka prywatnościKontakt