Floyd-Warshall voor alle paren

Soms heb je het kortste pad nodig tussen elk paar knopen, niet alleen vanaf één bron. Dat is het probleem van alle paren.

Floyd-Warshall vult met drie overzichtelijke geneste lussen een volledige afstandstabel voor alle paren, met vrijwel geen voorbereiding.

Gebruik een matrix waarin dist[i][j] de best bekende kosten van i naar j bevat. Initialiseer die met de directe kanten die je krijgt.

Elke knoop kan zichzelf gratis bereiken, dus zet je de diagonaal dist[i][i] op nul voordat je begint met relaxeren.

De truc is om paden door een tussenliggende knoop k te laten lopen en vervolgens te vragen of de route via k goedkoper is dan de directe route.

De buitenste lus is k, de gekozen tussenknoop. De binnenste lussen i en j proberen elk paar uit via die tussenknoop.

Relaxeer voor elk paar via k: als de route van i via k naar j korter is, werk je dist[i][j] bij naar die gecombineerde kosten.

Wanneer k klaar is, mogen alle paren tussenknopen tot en met k gebruiken. Door k als buitenste lus te gebruiken, blijft die garantie correct.

Floyd-Warshall accepteert negatieve kanten, maar geen negatieve cycli. Een negatieve cyclus zorgt ervoor dat een diagonaalelement kleiner dan nul wordt.

Drie lussen over n knopen geven een tijd van O(n^3) en een geheugenruimte van O(n^2), en zijn alleen praktisch wanneer n enkele honderden blijft.

Kies Floyd-Warshall wanneer de graaf klein en dicht is en je echt de afstand tussen elk paar nodig hebt, niet alleen die vanaf één bron.

Initialiseer een matrix, zet de diagonaal op nul en doorloop daarna k, i, j om via k te relaxeren. Kortste paden tussen alle paren in O(n^3). 🧮