Floyd Warshall Algorithm

ŚrednieNajkrótsze ścieżki Programowanie dynamiczne

+10

Dany jest graf skierowany z n wierzchołkami ponumerowanymi od 0 do n-1, przedstawiony jako macierz n na n: matrix[i][j] to waga krawędzi z wierzchołka i do wierzchołka j albo -1, jeśli taka krawędź nie istnieje, a matrix[i][i] wynosi 0. Długość ścieżki to suma wag jej krawędzi.

Zwróć macierz n na n, której element [i][j] jest długością najkrótszej ścieżki z wierzchołka i do wierzchołka j albo wynosi -1, jeśli z wierzchołka i nie można dotrzeć do wierzchołka j.

Funkcja

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: wagi krawędzi: matrix[i][j] to waga krawędzi od i do j albo -1, jeśli jej nie ma
Zwracainteger-2d-array: najkrótsza odległość dla każdej pary węzłów, -1, gdy nie ma ścieżki

Ograniczenia

1 ≤ n ≤ 100, gdzie n = matrix.length = matrix[i].length
matrix[i][i] = 0
Dla i ≠ j wartość matrix[i][j] wynosi -1 (brak krawędzi) lub 0 ≤ matrix[i][j] ≤ 1000.
Krawędzie są jednokierunkowe: matrix[i][j] i matrix[j][i] są niezależne.

Przykłady

Wejście: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
Wyjście: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
Wyjaśnienie: Przez węzeł 1 węzeł 0 dociera do węzła 2 za 6 zamiast 11, a do węzła 3 za 9. Węzeł 1 dociera do węzła 0 przez węzeł 2 za 3. Z węzła 3 nic nie wychodzi, więc jego wiersz ma wartość -1 poza przekątną.

Wejście: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
Wyjście: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
Wyjaśnienie: Krawędź z 2 do 1 ma wagę 0, więc 0 → 2 → 1 kosztuje 1, mniej niż bezpośrednia droga o koszcie 6. Z węzła 1 nie wychodzi żadna krawędź ani do węzła 0 nie wchodzi żadna krawędź, więc te pary pozostają równe -1.

Pytanie dodatkowe

Po zbudowaniu tablicy koszt jednej krawędzi spada. Czy możesz zaktualizować każdą odległość w czasie O(n²), zamiast ponownie wykonywać pętle O(n³)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Potrzebujesz najkrótszej ścieżki dla każdej pary węzłów. Algorytm Floyda-Warshalla znajduje wszystkie n² odpowiedzi za pomocą jednej potrójnej pętli. W każdej rundzie trasy mogą przebiegać przez o jeden węzeł więcej, a koszt to jedno porównanie dla każdej pary: najlepszej dotychczasowej trasy z trasą prowadzącą przez nowy węzeł.

Rozszerzaj każdą trasę o jedną krawędź, aż nic się nie zmieni

Poprawne, ale nie kończy się na największych testach

Intuicja

Zacznij od macierzy i w każdej iteracji wydłuż każdą trasę o jedną krawędź: trasa z i do m wraz z krawędzią m → j tworzy trasę z i do j, którą zachowujemy, jeśli jest krótsza. Powtarzaj, aż iteracja nie wprowadzi żadnych zmian.

Po p iteracjach znajdziesz każdą najkrótszą trasę o długości do p+1 krawędzi. Żadna waga nie jest ujemna, więc pewna najkrótsza trasa nie zawiera pętli i ma najwyżej n-1 krawędzi, a iteracje kończą się, gdy wszystkie odległości są ostateczne. Jedna iteracja to n³ = 10^6 kroków dla 100 węzłów, a długa sekwencja najkrótszych tras wymaga do n iteracji: O(n⁴), czyli do 10^8 kroków.

Algorytm

Skopiuj matrix do dist.
Dla każdego i, m i j: jeśli zarówno dist[i][m], jak i matrix[m][j] istnieją, oblicz ich sumę.
Jeśli dist[i][j] wynosi -1 lub jest większe od sumy, zapisz sumę i zapamiętaj, że przebieg coś zmienił.
Powtarzaj przebieg, aż niczego nie zmieni, a następnie zwróć dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall: pozwól na jeszcze jeden przystanek w każdej rundzie

Intuicja

Ogranicz węzły, na których trasa może się zatrzymać między jej końcami. Tabela początkowo zawiera macierz, czyli trasy bez przystanków. Po rundzie k wartość dist[i][j] oznacza najkrótszą trasę, której wszystkie przystanki znajdują się wśród węzłów od 0 do k, a ostatnia runda daje wynik.

W rundzie k najlepsza trasa, która może się również zatrzymać w k, albo pomija k — tabela już zawiera taką trasę — albo przechodzi przez k jeden raz, ponieważ żadna waga nie jest ujemna. Jej dwie części zatrzymują się tylko w węzłach od 0 do k-1, więc są to dist[i][k] i dist[k][j].

W pierwszym przykładzie runda 1 zastępuje bezpośrednią trasę o wadze 11 z węzła 0 do węzła 2 trasą o wadze 6. W rundzie 2 trasa z węzła 0 do węzła 3 ma długość 6 + 3 = 9, a przystanek w węźle 1 znajduje się na odcinku o długości 6.

Wystarczy jedna tabela: wiersz k i kolumna k nie zmieniają się w rundzie k, ponieważ dist[k][k] wynosi 0.

Algorytm

Skopiuj matrix do dist; -1 oznacza, że nie znaleziono jeszcze żadnej trasy.
Dla k od 0 do n-1 oraz dla każdego i i j: pomiń parę, jeśli dist[i][k] lub dist[k][j] wynosi -1.
W przeciwnym razie oblicz via = dist[i][k] + dist[k][j].
Jeśli dist[i][j] wynosi -1 lub jest większe niż via, ustaw je na via.
Zwróć dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

Pułapki i przypadki brzegowe

Dodawanie -1 tak, jakby była wagą: -1 + 5 = 4 wygląda jak trasa. Najpierw sprawdź obie części i traktuj -1 w dist[i][j] jako wartość gorszą niż dowolna trasa.
Umieszczanie pętli po k wewnątrz. Trasy przez przystanki od 0 do k-1 muszą być ustalone, zanim węzeł k zostanie uwzględniony.
Używanie największej wartości typu int jako nieskończoności: dodanie dwóch takich wartości powoduje przepełnienie 32-bitowego int i daje ujemną odległość. Rzeczywista odległość wynosi najwyżej 99 × 1000 = 99,000, więc 10^9 jest bezpieczne, ponieważ 2 × 10^9 jest mniejsze niż 2^31-1.
Zakładanie, że krawędzie działają w obie strony. W drugim przykładzie węzeł 0 dociera do węzła 1, ale z węzła 1 nie można dotrzeć nigdzie.
Uruchamianie przeszukiwania wszerz, które ignoruje wagi: w pierwszym przykładzie podaje ono 11 jako odległość z węzła 0 do węzła 2, a nie 6.

Najczęstsze pytania3

Jaka jest złożoność czasowa algorytmu Floyda-Warshalla?

Czas O(n³) dla n węzłów: trzy zagnieżdżone pętle iterujące po węzłach, z jednym dodawaniem i jednym porównaniem na krok, 10^6 kroków dla 100 węzłów. Złożoność pamięciowa wynosi O(n²) dla tabeli odległości, którą można aktualizować w miejscu.

Czy algorytm Floyda-Warshalla działa z ujemnymi wagami krawędzi?

Tak, o ile nie ma cyklu ujemnego, czyli pętli, której wagi sumują się do wartości mniejszej niż 0. Przy cyklu ujemnym najkrótsze ścieżki nie są określone, co pokazuje tabela: niektóre wartości dist[i][i] są mniejsze od 0.

Kiedy należy używać algorytmu Floyda-Warshalla zamiast algorytmu Dijkstry?

Użyj algorytmu Floyda-Warshalla dla każdej pary wierzchołków w gęstym grafie liczącym do kilkuset wierzchołków. Uruchomienie algorytmu Dijkstry z każdego wierzchołka ma koszt O(n³) przy użyciu tablicy i O(n · E log n) przy użyciu kopca, co sprawdza się lepiej w dużych, rzadkich grafach. Algorytm Floyda-Warshalla nie wymaga kopca i obsługuje ujemne krawędzie, w przeciwieństwie do algorytmu Dijkstry.

def shortestDistances(matrix):
    # Wpisz kod tutaj

Test #1

Test #2

Argument

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

Oczekiwany wynik

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]