Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Korteste vei mellom alle par, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
Å finne korteste vei mellom hvert par av noder i grafen samtidig.
En DP-algoritme som tillater stadig flere mellomnoder og finner alle-par-avstander i .
En node som korteste vei får lov til å passere gjennom. Floyd-Warshall utvider denne mengden trinnvis.
Den boolske matrisen som forteller om det finnes en rettet vei mellom hvert par av noder.
En -tabell der celle er korteste avstand fra til . Resultatet av en alle-par-algoritme.
Inndata-matrisen der celle er vekten på kanten fra til , eller uendelig om den mangler.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Floyd-Warshall-rekurrensen
Tillater stadig flere mellomnoder: korteste vei fra til gjennom er enten den uten , eller én som går via .
Floyd-Warshall, kjøretid
Tre nøstede løkker over alle nodetripler . Enkel å implementere og effektiv for tette grafer.
Gjentatt kvadrering av matriser
Ved å se korteste-vei-utvidelse som en matriseprodukt-lignende operasjon, og kvadrere, finner vi alle-par-avstander i logaritmisk mange runder.
Transitiv tillukning
Den boolske varianten av Floyd-Warshall: finnes det i det hele tatt en vei fra til ? Erstatter min/pluss med eller/og.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Forklare alle-par-problemet og når det lønner seg framfor å kjøre Dijkstra fra hver node
- 02Utlede Floyd-Warshall-rekurrensen ved å la stier bruke stadig flere mellomnoder, og forklare hvorfor k-løkka må ligge ytterst
- 03Implementere Floyd-Warshall i Theta(V^3) og oppdage negative sykler ved å se på diagonalen i avstandsmatrisen
- 04Forklare transitiv tillukning som den boolske varianten der min/pluss erstattes av eller/og