Korteste vei mellom alle par

Hele kartet på én gang

Tenk på et veikart med byer og veistrekninger der hver strekning har en lengde. alle-par-problemet handler om å fylle ut en hel reiseavstandstabell: for hvert par av byer, hvor langt er den korteste ruta? Det er noe annet enn å spørre om korteste vei fra én startby til resten. Her vil vi ha svaret for alle startpunkter samtidig.

En naiv idé er å kjøre en enkeltkilde-algoritme én gang per startnode. Med Dijkstra fra hver av de $V$ nodene får vi $\Theta (V\cdot E\lg V)$ — brukbart for tynne grafer med bare positive vekter. Men har grafen negative kanter, eller er den tett slik at $E$ nærmer seg $V^2$, lønner det seg å angripe alle par direkte. Det er det dette kapittelet handler om, og verktøyet er dynamisk programmering over matriser.

Vi representerer grafen med en vektmatrise $W$. Celle $W[i][j]$ er vekten på kanten fra node $i$ til node $j$. Finnes det ingen slik kant, setter vi $W[i][j]=\infty$, og avstanden fra en node til seg selv er $0$. Resultatet vi er ute etter er en avstandsmatrise $D$, der $D[i][j]$ er den korteste avstanden fra $i$ til $j$. Grafen under har fire noder, og til høyre står den ferdige avstandsmatrisen den gir.

Legg merke til at den direkte kanten fra node 1 til node 3 koster 8, men avstandsmatrisen sier 5. Den korteste ruta går via node 2: $1\to 2\to 3$ med kostnad $3+2$. Hele kunsten ligger i å oppdage slike omveier som faktisk er kortere. Symbolet $\infty$ i matrisen markerer par der ingen rettet vei finnes i det hele tatt.

Å bygge stier av kortere stier

Den sentrale ideen er at en lang sti kan settes sammen av to kortere. Hvis den korteste veien fra $i$ til $j$ går gjennom en node $k$ underveis, så består den av to deler: korteste vei fra $i$ til $k$, og korteste vei fra $k$ til $j$. Knekker vi en optimal sti på et mellompunkt, må begge halvdelene selv være optimale — ellers kunne vi byttet ut en halvdel med noe kortere og fått en enda kortere helsti. Dette er optimal delstruktur, og det er nettopp den egenskapen som gjør dynamisk programmering mulig.

En første DP-algoritme bygger på lengde: la $L^{(m)}[i][j]$ være den korteste avstanden fra $i$ til $j$ som bruker høyst $m$ kanter. For å utvide fra $m-1$ til $m$ kanter prøver vi alle mulige nest-siste noder:

for hver node i:
    for hver node j:
        L_ny[i][j] = L[i][j]
        for hver node k:
            if L[i][k] + W[k][j] < L_ny[i][j]:
                L_ny[i][j] = L[i][k] + W[k][j]

Dette ligner mistenkelig på matrisemultiplikasjon: i stedet for «gang og summer» gjør vi «adder og ta minimum». Siden en korteste vei uten negative sykler aldri bruker mer enn $V-1$ kanter, holder det å utvide $V-1$ ganger. Hver utvidelse er $\Theta (V^3)$, så hele denne «Slow-APSP» blir $\Theta (V^4)$ — riktig, men treig.

Trikset for å få den ned er at «matriseproduktet» er assosiativt. I stedet for å gange inn én ekstra kant av gangen, kan vi bruke gjentatt kvadrering: kvadrer matrisen for å doble kantbudsjettet hver runde. Etter $\lceil \lg (V-1)\rceil$ kvadreringer dekker vi alle stier. Det gir ƒgjentatt kvadrering av matriser, altså $\Theta (V^3\lg V)$. Bedre, men det finnes noe enda renere.

Floyd-Warshall: slipp til én mellomnode av gangen

floyd-warshall bytter perspektiv. I stedet for å telle kanter, nummererer vi nodene $1,2,\dots ,V$ og tillater stier å bruke stadig flere av dem som mellomnodeer underveis. La $d_{ij}^{(k)}$ være korteste avstand fra $i$ til $j$ der bare nodene $\{1,2,\dots ,k\}$ får brukes mellom endepunktene.

For hver $k$ stiller vi ett spørsmål om hver av de $V^2$ cellene: hjelper det å få lov til å bruke node $k$? Det er bare to muligheter. Enten holder vi oss til den beste ruta som klarte seg uten $k$, eller så går vi via $k$ — først korteste vei fra $i$ til $k$ (som allerede smetter gjennom $\{1,\dots ,k-1\}$), deretter fra $k$ til $j$. Vi tar det minste av de to:

ƒfloyd-warshall-rekurrensen

Basistilfellet $d_{ij}^{(0)}$, der ingen mellomnoder er lov, er rett og slett vektmatrisen $W$. Algoritmen blir tre nøstede løkker — den ytterste over $k$, de to indre over alle par $(i,j)$:

D = kopi av W            # ingen mellomnoder ennå
for k fra 0 til V-1:
    for i fra 0 til V-1:
        for j fra 0 til V-1:
            if D[i][k] + D[k][j] < D[i][j]:
                D[i][j] = D[i][k] + D[k][j]

Det fine her er at vi trygt kan oppdatere matrisen på plass. Når vi behandler runde $k$, leser vi rad $k$ og kolonne $k$ — men de endrer seg ikke i denne runden, fordi $d_{ik}^{(k)}=d_{ik}^{(k-1)}$ (en vei til $k$ vinner ingenting på å få lov til å bruke $k$ som mellomnode). Derfor trenger vi ikke to separate matriser; én holder.

At rekkefølgen på $k$ ligger ytterst er helt avgjørende. Vi låser opp én mellomnode om gangen, og når node $k$ slippes til, er alle stier som bare bruker lavere-nummererte mellomnoder allerede ferdig regnet. Bytter du om løkkene, mister du den garantien og kan få feil svar. Kjøretiden er ƒfloyd-warshall, kjøretid, $\Theta (V^3)$, med tre løkker over alle nodetripler. Den er like enkel som den er rask, og den slår per-node-Dijkstra på tette grafer.

Negative vekter og negative sykler

Floyd-Warshall takler negative kanter helt fint, så lenge grafen ikke har en negativ syklus. En negativ syklus er en rundtur der vektene summerer til noe under null. Da finnes det ingen veldefinert korteste avstand: du kan kjøre rundt en gang til og en gang til, og avstanden synker uten bunn.

Algoritmen gir oss en pen måte å oppdage dette på. Etter at den har kjørt ferdig, ser vi på diagonalen. Hvis noen $D[i][i]$ har blitt negativ, betyr det at det finnes en vei fra $i$ tilbake til $i$ med samlet negativ vekt — altså en negativ syklus som $i$ ligger på. En ren graf uten slike sykler skal ha bare nuller på diagonalen.

Når vi bare spør om det finnes en vei

Noen ganger bryr vi oss ikke om hvor langt, bare om det går an å komme fra $i$ til $j$ i det hele tatt. Det kalles transitiv tillukning: den boolske matrisen $T$ der $T[i][j]$ er sann hvis det finnes en rettet vei fra $i$ til $j$, og usann ellers.

Vi kan løse det med nøyaktig samme maskineri, men bytte ut tallregningen med logikk. Der Floyd-Warshall tok minimum av en sum, tar vi nå eller av en og: en vei fra $i$ til $j$ gjennom $\{1,\dots ,k\}$ finnes hvis den fantes uten $k$, eller hvis det både finnes en vei fra $i$ til $k$ og en fra $k$ til $j$.

ƒtransitiv tillukning

T = (W[i][j] != ∞)       # sann der det finnes en direkte kant
for k fra 0 til V-1:
    for i fra 0 til V-1:
        for j fra 0 til V-1:
            T[i][j] = T[i][j] or (T[i][k] and T[k][j])

Samme $\Theta (V^3)$, men hver celle er nå én bit i stedet for et tall, så arbeidet per celle er bittelite. Boolske operasjoner kan dessuten pakkes mange i et maskinord og kjøres parallelt, så i praksis er den transitive tillukningen ofte raskere enn den fulle avstandsversjonen.

Hvordan velge

Velg verktøy etter grafen. Er den tynn og har bare positive vekter, vinner som regel Dijkstra fra hver node. Er den tett, eller har den negative kanter, er Floyd-Warshall det enkleste og ofte raskeste valget — én kort trippelløkke, ingen prioritetskø, og avstandsmatrisen kommer ut ferdig utfylt. Trenger du bare å vite om noder kan nå hverandre, er den transitive tillukningen den lette boolske varianten av samme idé. Felles for dem alle er kjernen: lange korteste veier bygges av kortere korteste veier, og ved å slippe til én mellomnode om gangen fyller vi inn hele kartet i $\Theta (V^3)$.