Floyd-Warshall

O(V³)

Floyd-Warshall spočítá nejkratší cesty mezi všemi dvojicemi vrcholů jedním průchodem. Udržuje matici vzdáleností — dist[i][j] začíná jako přímá váha hrany (∞ pokud žádná není, 0 na diagonále) — a postupně bere každý vrchol k jako možnou mezizastávku: pokud je cesta i → k → j kratší než aktuální dist[i][j], převezme ji. Až každý vrchol přijde na řadu jako prostředek cesty, matice drží všechny nejkratší vzdálenosti. Trojitá smyčka běží v O(V³), což na hustých grafech překonává spuštění algoritmu z jednoho zdroje pro každý vrchol, a snese záporné hrany (ne však záporné cykly). Graf ukazuje aktuální mezivrchol k a koncové body; tabulka ukazuje, jak se vzdálenosti vyplňují.

Klik do prázdna = vrchol · klik na 2 vrcholy = hrana · táhni = posuňStart: A
Vstupní graf
DP tabulka
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Naplň matici přímými vahami hran (∞ pro chybějící hranu, 0 na diagonále).
  2. Vyber další vrchol k jako kandidáta na mezizastávku.
  3. Pro každou dvojici (i, j) zkontroluj, zda je i → k → j kratší než aktuální nejlepší.
  4. Pokud ano, aktualizuj dist[i][j]. Po každém k drží matice všechny nejkratší vzdálenosti.

Pseudokód

1floydWarshall(graph):               # O(V³)2  dist[i][j] ← edge weight, or ∞, 0 on the diagonal3  for each intermediate vertex k:4    for each pair (i, j):5      if dist[i][k] + dist[k][j] < dist[i][j]:6        dist[i][j] ← dist[i][k] + dist[k][j]   # route via k7  dist now holds every shortest distance