Floyd-Warshall: kortste paden tussen alle paren
Vul de afstandsmatrix voor alle knopenparen in met het Floyd-Warshall-algoritme met drie geneste lussen en gebruik die om het kleinste aantal hops tussen alle knopenparen te vinden.
Floyd-Warshall: kortste paden tussen alle paren is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 3 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Kortste paden tussen alle paren
Floyd-Warshall berekent kortste paden tussen elk paar knopen in een gewogen graaf — ook in grafen met negatieve gewichten van kanten, maar niet in grafen met negatieve cycli. Dijkstra vanaf elke bron uitvoeren kost O(V × (V+E) log V); Floyd-Warshall werkt in O(V³)
Het kernidee: tussenliggende knopen
Het inzicht achter Floyd-Warshall: dp[i][j][k] = het kortste pad van i naar j waarbij alleen knopen uit {0, 1, ..., k} als tussenliggende knopen worden gebruikt. Ofwel gebruikt het kortste pad knoop k als tussenliggende knoop, ofwel niet. Als dat wel zo is: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Als dat niet zo is: dp[i][j][k] = dp[i][j][k-1]. Omdat de derde dimensie alleen vooruitgaat, kan die worden geëlimineerd — we werken de waarden direct bij.
De afstandsmatrix initialiseren
Begin met een V×V-matrix: dist[i][i] = 0 (nul afstand van een knoop naar zichzelf), dist[i][j] = weight voor directe kanten en dist[i][j] = inf voor paren zonder kant. Doorloop daarna alle tussenliggende knopen k en werk de paren (i, j) bij. De buitenste lus over k moet eerst komen, zodat we paden correct opbouwen via een steeds grotere verzameling toegestane tussenliggende knopen.
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 distVolledige implementatie met voorbeeld
Laten we Floyd-Warshall uitvoeren op een graaf met vier knopen. Nadat elke tussenliggende knoop k is verwerkt, bevat de matrix kortere paden die via knoop k lopen. Het algoritme verwerkt meerdere sprongen vanzelf door kortste paden stapsgewijs op te bouwen.
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])Negatieve cycli detecteren
Controleer na het uitvoeren van Floyd-Warshall de hoofddiagonaal: als voor een dist[i][i] < 0 geldt, loopt er een negatieve cyclus door knoop i. Dat komt doordat je met een negatieve cyclus van i naar i kunt gaan tegen negatieve kosten. Als er geen negatieve cyclus is, blijven alle diagonaalelementen 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)) # TruePaden reconstrueren
Houd een matrix next[i][j] bij om het daadwerkelijke pad van i naar j te reconstrueren: initialiseer voor directe kanten next[i][j] = j. Stel bij het bijwerken via tussenliggende knoop k next[i][j] = next[i][k] in. Begin bij i en volg de verwijzingen in next tot je j bereikt om het pad terug te vinden. Dit voegt O(V²) ruimte en O(V) per padreconstructie toe.
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 pathTransitieve afsluiting
Een eenvoudigere variant: Transitieve afsluiting beantwoordt voor alle paren de vraag 'is knoop j bereikbaar vanaf knoop i?'. Vervang afstanden door booleaanse waarden: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Dit is Floyd-Warshall met booleaanse OF in plaats van optellen en het minimum nemen. Initialiseer reach[i][i] = True en reach[i][j] = True voor directe kanten.
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)Complexiteit en toepassingsmoment
Floyd-Warshall: O(V³) tijd, O(V²) ruimte. Voor dichte grafen (E ≈ V²) met V ≤ 300 is dit sneller dan Dijkstra V keer uitvoeren, wat in dat geval ook O(V³) kost. Voor ijle grafen met V = 1000 en E = 3000 kost V keer Dijkstra uitvoeren O(V×E×log V) ≈ 33M, terwijl Floyd-Warshall O(V³) = 10⁹ kost — Dijkstra wint. Weet wanneer je elk algoritme gebruikt.
Minimumaantal sprongen tussen alle paren
Stel alle gewichten van de kanten in op 1 (of gebruik een booleaanse adjacentiematrix met Floyd-Warshall waarbij je optelt in plaats van het minimum neemt): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Hiermee bereken je het minimumaantal sprongen tussen elk paar — het resultaat van BFS voor alle paren, maar berekend met één O(V³)-passage van Floyd-Warshall.
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]Wanneer je tijdens een sollicitatiegesprek naar Floyd-Warshall wordt gevraagd
Floyd-Warshall komt aan bod bij sollicitatievragen over: (1) afstanden tussen alle paren in een kleine graaf, (2) nagaan of er een cyclus bestaat met een negatief totaalgewicht, (3) kortste paden berekenen in problemen met het doorgeven van beperkingen, en (4) problemen die expliciet om oplossingen van O(V³) vragen waarbij V ≤ 200. Noem altijd de structuur met drie lussen en de vereiste dat er geen negatieve cycli zijn voor correctheid.
Ongerichte grafen met Floyd-Warshall
Voeg voor ongerichte grafen beide richtingen toe voor elke kant: dist[u][v] = dist[v][u] = weight. De rest van het algoritme is identiek. De resulterende matrix is symmetrisch: dist[i][j] == dist[j][i] voor alle paren. Let bij het initialiseren goed op dat je niet per ongeluk gerichte kanten toewijst — ongerichte kanten moeten in beide richtingen aan de beginmatrix worden toegevoegd voordat je de drie lussen uitvoert.
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 distSnelle controle
Test je begrip van de concepten Data Structures & Algorithms — Coding Interview Prep uit deze les.
Samenvatting van de les
In deze les heb je geleerd: Floyd-Warshall berekent de kortste paden tussen alle paren met drie geneste lussen en de recurrentie dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), je kunt negatieve cycli detecteren door na afloop te controleren of een dist[i][i] < 0 is, en het algoritme werkt in O(V³)-tijd en gebruikt O(V²)-ruimte. Hierna bekijken we opnieuw toepassingen van kortste paden met Network Delay Time en technieken voor padreconstructie.
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Floyd-Warshall: kortste paden tussen alle paren” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “Floyd-Warshall: kortste paden tussen alle paren”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat leer ik in “Floyd-Warshall: kortste paden tussen alle paren”?
Vul de afstandsmatrix voor alle knopenparen in met het Floyd-Warshall-algoritme met drie geneste lussen en gebruik die om het kleinste aantal hops tussen alle knopenparen te vinden. Je oefent met DSA Interview Prep door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met DSA Interview Prep te beginnen?
Ervaring vooraf is niet nodig. DSA Interview Prep op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 3 van 4.
Hoe lang duurt de les “Floyd-Warshall: kortste paden tussen alle paren”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over DSA Interview Prep?
Ja. Elke les over DSA Interview Prep bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Dijkstra's algoritme met een priority queue
- Bellman-Ford en negatieve cycli
- Floyd-Warshall: kortste paden tussen alle paren
- Network Delay Time en padreconstructie