Korteste vei fra alle til alle

Til nå har vi funnet korteste vei fra én kilde. Nå skal vi løse alle par på én gang. Det virker som $V$ kjøringer av en énkilde-algoritme, men når alle par skal løses blir de overlappende delinstansene synlige — og dynamisk programmering blir det naturlige verktøyet, spesielt på tette grafer.

Problemet og forgjengerstrukturen

Alle-til-alle korteste veier (APSP) tar en vektet rettet graf og spør om den korteste avstanden $d_{ij}$ mellom hvert par av noder $i$ og $j$ . Resultatet er naturlig en $V \times V$ -matrise.

For å kunne rekonstruere selve veiene holder vi en forgjengermatrise $\Pi$ : $\pi_{ij}$ er forgjengeren til $j$ på en korteste vei fra $i$ . Der énkilde-algoritmer har ett forgjengertre, har APSP altså ett tre per startnode, samlet i én matrise. Negative kanter er tillatt så lenge det ikke finnes negative sykler.

Fra matrise-«multiplikasjon» til Floyd-Warshall

En første DP bygger korteste veier etter antall kanter de bruker. La $L^{(m)}_{ij}$ være korteste vei fra $i$ til $j$ som bruker høyst $m$ kanter. Da er

L^{(m)}_{ij} = \min_{k}\left\{\, L^{(m-1)}_{ik} + w_{kj} \,\right\},

som er nøyaktig matrise-«multiplikasjon» der $+$ erstatter $\times$ og $\min$ erstatter $\sum$ . Siden en enkel vei har høyst $V-1$ kanter, gir gjentatt «multiplikasjon» svaret. Slow-APSP gjør dette $V-1$ ganger i $\Theta(V^4)$ ; Faster-APSP bruker gjentatt kvadrering ( $L^{(2m)}$ fra $L^{(m)}$ ) og kommer ned i $\Theta(V^3 \lg V)$ .

Floyd-Warshall bytter ut DP-dimensjonen: i stedet for antall kanter teller vi hvilke mellomliggende noder veien får lov til å bruke.

Hvert lag $k$ vurderer altså om det å slippe inn node $k$ som mellomstasjon korter ned noen vei. Tre nøstede løkker over $k$ , $i$ og $j$ gir kjøretiden:

\Theta(V^3)

— $\Theta(V^3)$ , uavhengig av hvor mange kanter grafen har. Det slår $V$ Dijkstra-kjøringer på tette grafer og håndterer i tillegg negative kanter.

DP-lagene i arbeid

Tabellen under viser et lite eksempel: avstandsmatrisen for fire noder mens vi slipper inn én og én mellomliggende node. Celler som forbedres når node $k$ åpnes, er markert.

$d^{(k)}$	$1\to 2$	$1\to 3$	$1\to 4$	$4\to 2$
$k=0$ (kun kanter)	$\infty$	$3$	$\infty$	$\infty$
$k=1$ (via $1$ )	$\infty$	$3$	$\infty$	$\infty$
$k=2$ (via $2$ )	$\infty$	$3$	$\infty$	$\infty$
$k=3$ (via $3$ )	$\mathbf{7}$	$3$	$\mathbf{8}$	$\infty$
$k=4$ (via $4$ )	$7$	$3$	$8$	$\mathbf{2}$

Hvert lag åpner én ny mellomliggende node. Når node

3

slippes inn finnes en vei

1\\to 3\\to 2

; node

4

åpner

4\\to 2

. Fete celler ble forbedret i akkurat det laget.

I praksis trenger vi bare én matrise: oppdateringen $d_{ij} \leftarrow \min(d_{ij},\, d_{ik} + d_{kj})$ kan gjøres på stedet, fordi rad $k$ og kolonne $k$ ikke endrer seg i runde $k$ .

Initialiser

Sett $d_{ij} = w_{ij}$ for kanter, $0$ på diagonalen og $\infty$ ellers. La $\pi_{ij} = i$ der det finnes en kant, ellers udefinert.
For hver mellomliggende node $k = 1 \dots V$

Vurder for alle par $(i, j)$ om veien $i \to k \to j$ er kortere enn den nåværende $d_{ij}$ .
Oppdater hvis det lønner seg

Hvis $d_{ik} + d_{kj} < d_{ij}$ : sett $d_{ij} = d_{ik} + d_{kj}$ og $\pi_{ij} = \pi_{kj}$ (forgjengeren arves fra den andre halvdelen av veien).
Les av

Etter $k = V$ inneholder $d$ alle korteste avstander, og $\pi$ lar deg rekonstruere hver vei.

Transitiv tillukning

Trenger vi bare å vite om det finnes en vei fra $i$ til $j$ — ikke hvor lang — kjører vi Transitive-Closure: samme tre løkker, men med boolske verdier i stedet for avstander. Rekurrensen blir

t^{(k)}_{ij} = t^{(k-1)}_{ij} \;\lor\; \left( t^{(k-1)}_{ik} \land t^{(k-1)}_{kj} \right).

Med $\min/+$ byttet ut med $\lor/\land$ slipper vi å regne på vekter, og bitoperasjoner gjør det svært raskt i praksis.