Masz wątpliwości, czy wybrać najkrótszą ścieżkę od lokalizacji do miejsca docelowego? Następnie, powinieneś wiedzieć o tym algorytmie.
- Algorytm Floyda-Warshalla jest używany do znalezienia najkrótszych ścieżek między wszystkimi parami wierzchołków w grafie, gdzie każda krawędź w grafie ma wagę, która jest dodatnia lub ujemna.
- Największą zaletą stosowania tego algorytmu jest to, że wszystkie najkrótsze odległości między dwoma dowolnymi wierzchołkami można obliczyć w czasie O(V3), gdzie V jest liczbą wierzchołków w grafie.
- Algorytm Floyda-Warshalla jest również nazywany algorytmem Floyda, algorytmem Roya-Floyda, algorytmem Roya-Warshalla lub algorytmem WFI.
- Algorytm ten stosuje podejście programowania dynamicznego do znajdowania najkrótszych ścieżek.
Algorytm
Dla grafu z N wierzchołkami:
Krok 1: Zainicjuj najkrótsze ścieżki między dowolnymi 2 wierzchołkami z nieskończonością.
Krok 2: Znajdź wszystkie pary najkrótszych ścieżek, które używają 0 pośrednich wierzchołków, następnie znajdź najkrótsze ścieżki, które używają 1 pośredniego wierzchołka i tak dalej… aż do użycia wszystkich N wierzchołków jako węzłów pośrednich.
Krok 3: Zminimalizuj najkrótsze ścieżki między dowolnymi 2 parami w poprzedniej operacji.
Krok 4: Dla dowolnych 2 wierzchołków (i,j) , należy faktycznie zminimalizować odległości między tą parą przy użyciu pierwszych K węzłów, więc najkrótsza ścieżka będzie: min(dist+dist,dist).
dist reprezentuje najkrótszą ścieżkę, która używa tylko pierwszych K wierzchołków, dist reprezentuje najkrótszą ścieżkę między parą k,j. Ponieważ najkrótsza ścieżka będzie konkatenacją najkrótszej ścieżki z i do k, a następnie z k do j.
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist = min( dist, dist + dist );
}
}
}
Przykład
Niech dany graf będzie:
Prześledź poniższe kroki, aby znaleźć najkrótszą ścieżkę między wszystkimi parami wierzchołków.
- Utwórz macierz
A0o wymiarzen*n, gdzie n jest liczbą wierzchołków. Wiersz i kolumna są indeksowane odpowiednio jako i oraz j. i oraz j są wierzchołkami grafu.
Każda komórka A jest wypełniona odległością od wierzchołka ith do wierzchołka jth. Jeśli nie ma drogi od ith wierzchołka do jth wierzchołka, komórkę pozostawiamy jako nieskończoność.
2.Teraz utwórz macierz A1 korzystając z macierzy A0. Elementy w pierwszej kolumnie i pierwszym wierszu pozostawiamy bez zmian. Pozostałe komórki są wypełniane w następujący sposób.
Pozwól k być wierzchołkiem zamrażającym w najkrótszej ścieżce od źródła do celu. W tym kroku k jest pierwszym wierzchołkiem.A wypełniamy (A + A) if (A > A + A).
To znaczy, że jeśli bezpośrednia odległość od źródła do celu jest większa niż droga przez wierzchołek k, to komórkę wypełniamy A + A.
W tym kroku k jest wierzchołkiem 1. Obliczamy odległość od wierzchołka źródłowego do wierzchołka docelowego przez ten wierzchołek k.
Na przykład: Dla A1 bezpośrednia odległość od wierzchołka 2 do 4 wynosi 4, a suma odległości od wierzchołka 2 do 4 przez wierzchołek (czyli od wierzchołka 2 do 1 i od wierzchołka 1 do 4) wynosi 7. Skoro 4 < 7, to A0 wypełniamy 4.
3 W podobny sposób A2 tworzymy za pomocą A3. Elementy w drugiej kolumnie i drugim wierszu pozostawiamy tak jak są.
W tym kroku k jest drugim wierzchołkiem (czyli wierzchołkiem 2). Pozostałe kroki są takie same jak w kroku 2.
4.Podobnie tworzone są również A3 i A4.
A4 daje najkrótszą ścieżkę między każdą parą wierzchołków.
Zakłopotany, aby wybrać najkrótszą ścieżkę, a następnie użyć poniższego kodu, aby ją znaleźć. Ale wprowadź poprawne odległości.
Złożoność czasowa
Istnieją trzy pętle. Każda pętla ma stałą złożoność. Zatem złożoność czasowa algorytmu Floyda-Warshalla wynosi O(n3).
Złożoność przestrzenna
Złożoność przestrzenna algorytmu Floyda-Warshalla wynosi O(n2).
.