Floyd-Warshall: najkrótsze ścieżki między wszystkimi parami wierzchołków
Wypełniać macierz odległości między wszystkimi parami wierzchołków za pomocą algorytmu Floyd-Warshalla z trzema zagnieżdżonymi pętlami oraz stosować go do znajdowania najmniejszej liczby przeskoków między każdą parą wierzchołków
Floyd-Warshall: najkrótsze ścieżki między wszystkimi parami wierzchołków to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Najkrótsze ścieżki między wszystkimi parami wierzchołków
Algorytm Floyda-Warshalla oblicza najkrótsze ścieżki między każdą parą wierzchołków w grafie ważonym — w tym w grafach z ujemnymi wagami, ale bez ujemnych cykli. Uruchomienie algorytmu Dijkstry z każdego źródła zajmuje O(V × (V+E) log V), natomiast algorytm Floyda-Warshalla działa w czasie O(V³), niezależnie od gęstości grafu. W przypadku gęstych grafów, dla V ≤ 500, algorytm Floyda-Warshalla jest często prostszy i porównywalnie szybki.
Główna idea: wierzchołki pośrednie
Najważniejsza idea algorytmu Floyda-Warshalla: dp[i][j][k] = najkrótsza ścieżka z i do j, wykorzystująca wyłącznie wierzchołki {0, 1, ..., k} jako pośrednie. Najkrótsza ścieżka albo wykorzystuje wierzchołek k jako pośredni, albo go nie wykorzystuje. Jeśli go wykorzystuje: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Jeśli nie: dp[i][j][k] = dp[i][j][k-1]. Ponieważ trzeci wymiar postępuje wyłącznie do przodu, można go wyeliminować — aktualizujemy wartości w miejscu.
Inicjalizacja macierzy odległości
Należy rozpocząć od macierzy V×V: dist[i][i] = 0 (zerowa odległość od wierzchołka do samego siebie), dist[i][j] = weight dla krawędzi bezpośrednich oraz dist[i][j] = inf dla par niepołączonych krawędzią. Następnie należy iterować po wszystkich wierzchołkach pośrednich k, aktualizując pary (i, j). Zewnętrzna pętla po k musi znajdować się na zewnątrz, aby prawidłowo budować ścieżki przez coraz większy zbiór dozwolonych wierzchołków pośrednich.
def floyd_warshall(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w # directed graph
for k in range(V): # intermediate node
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return distKompletna implementacja z przykładem
Prześledźmy działanie algorytmu Floyda-Warshalla na grafie z 4 wierzchołkami. Po przetworzeniu każdego wierzchołka pośredniego k macierz uzupełnia się o krótsze ścieżki przebiegające przez wierzchołek k. Algorytm w naturalny sposób obsługuje wiele przejść, stopniowo budując najkrótsze ścieżki.
def floyd_warshall(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] != INF and dist[k][j] != INF:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
V = 4
edges = [(0,1,3),(0,2,7),(1,2,1),(1,3,5),(2,3,2)]
dist = floyd_warshall(V, edges)
for row in dist:
print([x if x != float('inf') else 'INF' for x in row])Wykrywanie ujemnych cykli
Po uruchomieniu algorytmu Floyda-Warshalla należy sprawdzić główną przekątną: jeśli dla dowolnego dist[i][i] < 0, istnieje ujemny cykl przechodzący przez wierzchołek i. Wynika to z faktu, że ujemny cykl umożliwia dotarcie z i do i przy ujemnym koszcie. Jeśli nie istnieje żaden ujemny cykl, wszystkie elementy na przekątnej pozostają równe 0.
def has_negative_cycle_fw(V, edges):
dist = floyd_warshall(V, edges)
for i in range(V):
if dist[i][i] < 0:
return True # negative cycle through node i
return False
# Negative cycle: 0->1->2->0 with weights 1,-3,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-3),(2,0,1)]
print(has_negative_cycle_fw(3, edges_neg)) # TrueOdtwarzanie ścieżki
Aby odtworzyć rzeczywistą ścieżkę z i do j, należy utrzymywać macierz next[i][j]: początkowo next[i][j] = j dla krawędzi bezpośrednich. Podczas aktualizowania przez wierzchołek pośredni k należy ustawić next[i][j] = next[i][k]. Aby odzyskać ścieżkę, należy rozpocząć od i i podążać za wskaźnikami next aż do osiągnięcia j. Wymaga to dodatkowej przestrzeni O(V²) oraz O(V) na odtworzenie każdej ścieżki.
def fw_with_path(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
nxt = [[None]*V for _ in range(V)]
for i in range(V): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w; nxt[u][v] = v
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
nxt[i][j] = nxt[i][k]
return dist, nxt
def get_path(nxt, i, j):
if nxt[i][j] is None: return []
path = [i]
while i != j:
i = nxt[i][j]; path.append(i)
return pathDomknięcie przechodnie
Prostszy wariant: domknięcie przechodnie odpowiada dla wszystkich par na pytanie „czy wierzchołek j jest osiągalny z wierzchołka i?”. Odległości zastępuje się wartościami logicznymi: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Jest to algorytm Floyda-Warshalla z logicznym OR zamiast dodawania i minimum. Należy zainicjalizować reach[i][i] = True oraz reach[i][j] = True dla krawędzi bezpośrednich.
def transitive_closure(V, edges):
reach = [[False]*V for _ in range(V)]
for i in range(V):
reach[i][i] = True
for u, v, _ in edges:
reach[u][v] = True
for k in range(V):
for i in range(V):
for j in range(V):
reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
return reach
edges = [(0,1,1),(1,2,1)]
R = transitive_closure(3, edges)
print(R[0][2]) # True (0 can reach 2 via 0->1->2)Złożoność i kiedy stosować
Algorytm Floyda-Warshalla: czas O(V³), przestrzeń O(V²). Dla gęstych grafów (E ≈ V²) z V ≤ 300 jest szybszy niż uruchomienie algorytmu Dijkstry V razy (w tym przypadku również O(V³)). Dla rzadkich grafów z V = 1000 i E = 3000 uruchomienie algorytmu Dijkstry V razy kosztuje O(V×E×log V) ≈ 33M, podczas gdy algorytm Floyda-Warshalla kosztuje O(V³) = 10⁹ — wygrywa algorytm Dijkstry. Należy wiedzieć, kiedy zastosować każdy z nich.
Minimalna liczba przejść między każdą parą
Ustaw wszystkie wagi krawędzi na 1 (lub użyj boolowskiej macierzy sąsiedztwa z algorytmem Floyd-Warshall, stosując dodawanie zamiast funkcji min): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Oblicza to minimalną liczbę przejść między każdą parą — wynik BFS dla wszystkich par, ale uzyskany za pomocą pojedynczego przebiegu algorytmu Floyd-Warshall o złożoności O(V³).
def min_hops_all_pairs(V, adj_list):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for j in adj_list[i]:
dist[i][j] = 1
for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
adj = [[1,2],[2],[3],[],[]]
print(min_hops_all_pairs(5, adj)[0]) # [0, 1, 1, 2, INF]Kontekst rozmowy kwalifikacyjnej: kiedy rekruterzy pytają o algorytm Floyd-Warshall
Algorytm Floyd-Warshall pojawia się na rozmowach kwalifikacyjnych w zadaniach dotyczących: (1) odległości między wszystkimi parami w małym grafie, (2) sprawdzania, czy istnieje cykl o ujemnej sumie wag, (3) wyznaczania najkrótszych ścieżek w problemach propagacji ograniczeń oraz (4) zadań, które wprost wymagają rozwiązań O(V³), gdzie V ≤ 200. Zawsze należy wspomnieć o strukturze trzech pętli oraz o konieczności braku ujemnych cykli, aby wynik był poprawny.
Grafy nieskierowane z algorytmem Floyd-Warshall
W przypadku grafów nieskierowanych należy dodać oba kierunki dla każdej krawędzi: dist[u][v] = dist[v][u] = weight. Reszta algorytmu pozostaje bez zmian. Wynikowa macierz jest symetryczna: dist[i][j] == dist[j][i] dla każdej pary. Podczas inicjalizacji należy uważać, aby przypadkowo nie przypisać krawędziom kierunku — krawędzie nieskierowane muszą zostać dodane w obu kierunkach do macierzy początkowej przed uruchomieniem trzech pętli.
def fw_undirected(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
dist[v][u] = w # both directions for undirected
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return distSzybkie sprawdzenie
Proszę sprawdzić swoją znajomość zagadnień dotyczących struktur danych i algorytmów — przygotowania do rozmów kwalifikacyjnych z programowania — omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo: algorytm Floyd-Warshall wyznacza najkrótsze ścieżki między wszystkimi parami za pomocą trzech zagnieżdżonych pętli i rekurencji dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), ujemne cykle można wykryć, sprawdzając po zakończeniu działania algorytmu, czy dla któregoś i zachodzi dist[i][i] < 0, a także że algorytm działa w czasie O(V³) i zajmuje O(V²) pamięci. Następnie wrócimy do zastosowań algorytmów najkrótszej ścieżki, omawiając Network Delay Time oraz techniki odtwarzania ścieżki.
Ucz się Python dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 30
- Lekcje
- 120
Często zadawane pytania
Czy lekcja „Floyd-Warshall: najkrótsze ścieżki między wszystkimi parami wierzchołków” jest bezpłatna?
Tak — pełny tekst „Floyd-Warshall: najkrótsze ścieżki między wszystkimi parami wierzchołków” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Floyd-Warshall: najkrótsze ścieżki między wszystkimi parami wierzchołków”?
Wypełniać macierz odległości między wszystkimi parami wierzchołków za pomocą algorytmu Floyd-Warshalla z trzema zagnieżdżonymi pętlami oraz stosować go do znajdowania najmniejszej liczby przeskoków m… Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Floyd-Warshall: najkrótsze ścieżki między wszystkimi parami wierzchołków”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Algorytm Dijkstry z kolejką priorytetową
- Bellman-Ford i cykle ujemne
- Floyd-Warshall: najkrótsze ścieżki między wszystkimi parami wierzchołków
- Opóźnienie sieci i odtwarzanie ścieżki