4.4 Alle-til-alle korteste vei

`Floyd-Warshall` (`d`- og `π`-regel), `Slow-APSP` (min-pluss-produkt) og `Transitive-Closure` — matrisebaserte APSP-algoritmer.

50 min

6 oppgaver

Alle-til-alle korteste vei

Din fremgang i kapitlet

0 / 6 oppgaver

Kapitlets plass i kurset

Bygger på

4.3Korteste vei fra én kilde — Dijkstra, Bellman-Ford, DAG

Brukes videre i

4.5DRILL — Håndkjøring av grafalgoritmer

Alle-til-alle korteste vei er registrert i 11 av de 17 settene i grunnlaget
(65 %). Grunnlaget er de 17 settene fra august 2015 til august 2023 som er
gjennomgått tema for tema — det er nevneren hver gang boka oppgir en prosent.

Prioritet: kjenne til. Men temaet differensierer i toppen, og det er verdt
å merke seg hvorfor: håndkjøringen er helt mekanisk, og den som har regnet
gjennom to runder på forhånd, får poengene på fem minutter.

To sjangre henter fra kapitlet:

- Sjanger C — håndkjøring, altså at du utfører algoritmen steg for steg og
oppgir bare det etterspurte. Her er det en matrise som etterspørres, og
ofte bare for én bestemt runde k eller én bestemt celle.
- Sjanger E — kjøretidskunnskap, altså at du oppgir kjøretiden i det
strammeste uttrykket som er riktig. $\Theta(V^3)$ for Floyd-Warshall er et
av de tallene som skal kunne skrives ned kaldt.

De to fellene som koster mest i dette kapitlet:

1. Å bruke vanlig matriseprodukt i Slow-APSP. Produktet der er
min-pluss: du tar minimum av summer, ikke summen av produkter.
2. Å blande d-regelen og π-regelen i Floyd-Warshall. De oppdateres
samtidig, men etter forskjellige regler — og π-regelen arver fra rad
k, ikke fra rad i.

Slik er kapitlet lagt opp (50 min):

Innhold	Tid
Hvorfor et eget alle-til-alle-problem	ca. 7 min
`Floyd-Warshall`: `d`-regelen og `π`-regelen	ca. 20 min
`Slow-APSP` og min-pluss-produktet	ca. 14 min
`Transitive-Closure` og utskrift av stien	ca. 9 min

Forkunnskaper

- kap. 4.3 — korteste vei fra én kilde. Dette sto der:
Dijkstra er $O(E\lg V)$ og krever ikke-negative kantvekter;
Bellman-Ford er $\Theta(VE)$ , tåler negative kanter og oppdager negative
sykler. Begge bygger på slakking: hvis $d[u] + w(u,v) < d[v]$ , er den
nye veien bedre, og $d[v]$ og $\pi[v]$ oppdateres.
- kap. 4.1 — grafrepresentasjon. Vi bruker
nabomatrisen her, ikke nabolister: algoritmene i dette kapitlet arbeider
direkte på en $V \times V$ -matrise.
- kap. 1.1 — de asymptotiske symbolene.

Ett nytt begrep innføres underveis: mellomnode. Det er den eneste ideen du
trenger utover kap. 4.3.

Notasjons- og pseudokodeliste

Hvorfor et eget alle-til-alle-problem (~7 min)

En rutetjeneste skal vise reisetiden mellom alle par av holdeplasser, ikke
bare fra én. Den enkle løsningen er å kjøre Dijkstra én gang per node: $V$
kjøringer à $O(E\lg V)$ , altså $O(VE\lg V)$ .

For en glissen graf, der $E$ er omtrent like stor som $V$ , er det et godt
valg. For en tett graf, der $E$ nærmer seg $V^2$ , blir det $O(V^3\lg V)$ —
og da finnes noe bedre. Floyd-Warshall gjør jobben i $\Theta(V^3)$ , uten
logaritmefaktor og uten prioritetskø.

Og det finnes en grunn til: Dijkstra krever ikke-negative kantvekter. Har
grafen negative kanter, må du bruke Bellman-Ford per node, og det koster
$\Theta(V^2E)$ . Floyd-Warshall tåler negative kanter uten videre.

Alle-til-alle korteste vei

V \times V

Mellomnode

1 \to 2 \to 3 \to 4

`Floyd-Warshall`: `d`-regelen og `π`-regelen (~20 min)

Ideen er å stille ett spørsmål av gangen: hvor korte blir stiene hvis bare
node 1 får være mellomnode? Så: hvis bare node 1 og 2 får det? Og så videre,
til alle nodene er tillatt.

La $d^{(k)}_{ij}$ være den korteste avstanden fra $i$ til $j$ når bare nodene
$1, 2, \dots, k$ er tillatt som mellomnoder. Da er $d^{(0)}$ selve
vektmatrisen — ingen mellomnoder er tillatt, så bare direkte kanter teller — og
$d^{(V)}$ er svaret.

Overgangen fra $k-1$ til $k$ er ett enkelt valg: enten går den korteste stien
gjennom node $k$ , eller så gjør den det ikke.

📜Pseudokode-kontrakt: `Floyd-Warshall`

Antagelser om representasjon. Grafen er gitt som en vektmatrise
W[1..n][1..n] med W[i][i] = 0, W[i][j] = w(i,j) når kanten finnes, og
INF ellers. Nodene er nummerert 1 til

n = |V|

. Negative kantvekter er
tillatt; negative sykler er ikke.

Prebetingelse: grafen har ingen negativ sykel.
Postbetingelse: d[i][j] er den korteste avstanden fra i til j, og
pi[i][j] er forgjengeren til j på en korteste sti fra i.

Floyd-Warshall(W)
  Input:  vektmatrisen W[1..n][1..n]
  Output: avstandsmatrisen d og forgjengermatrisen pi
  d = W
  for i = 1 to n
      for j = 1 to n
          if i != j and W[i][j] < INF
              pi[i][j] = i
          else
              pi[i][j] = NIL
  for k = 1 to n
      for i = 1 to n
          for j = 1 to n
              if d[i][k] + d[k][j] < d[i][j]
                  d[i][j] = d[i][k] + d[k][j]
                  pi[i][j] = pi[k][j]
  return d, pi
  Kjoeretid: Theta(V^3)

Invarianten i én setning: etter runde k inneholder d[i][j] den korteste
avstanden fra i til j blant alle stier som bare bruker nodene 1 til k
som mellomnoder.

d-regelen og π-regelen er ikke den samme regelen. d tar minimum av
den gamle verdien og veien om k. π beholder den gamle forgjengeren så lenge
den gamle veien er minst like kort — og arver pi[k][j] når veien om k
vinner. Legg merke til at den arvede verdien hentes fra rad k, ikke fra
rad i: den siste kanten inn til j er den samme som på den korteste stien
fra k til j.

Kjøretid: tre nøstede løkker over $n = |V|$ , med konstant arbeid innerst,
altså $\Theta(V^3)$ . Grensen er tett: løkkene kjører alltid ferdig, uansett
graf.

Rekkefølgen på løkkene er ikke likegyldig. k må være den ytterste.
Bytter du om, brytes invarianten, og resultatet blir galt.

✏️Eksempel 1: To runder av `Floyd-Warshall`

Et internt transportnett har fire terminaler nummerert 1 til 4, med disse
enveis-strekningene og kjøretidene:

$1 \to 2$ (3), $1 \to 4$ (7), $2 \to 1$ (8), $2 \to 3$ (2), $3 \to 4$ (1),
$4 \to 1$ (2).

a) Skriv opp vektmatrisen $W = d^{(0)}$ og den tilhørende $\pi^{(0)}$ .
b) Utfør runden med $k = 1$ .
c) Utfør runden med $k = 2$ , og oppgi begge matrisene.

a) Diagonalen er 0, og

\infty

står der det ikke går noen strekning.

$d^{(0)} = W$

1	2	3	4
1	0	3	$\infty$	7
2	8	0	2	$\infty$
3	$\infty$	$\infty$	0	1
4	2	$\infty$	$\infty$	0

$\pi^{(0)}$

1	2	3	4
1	NIL	1	NIL	1
2	2	NIL	2	NIL
3	NIL	NIL	NIL	3
4	4	NIL	NIL	NIL

\pi^{(0)}

står i selv som forgjenger overalt der det finnes en direkte
kant — den korteste kjente stien fra i til j er da kanten, og forgjengeren
til j er i.

b) Med $k = 1$ ser vi etter stier $i \to 1 \to j$ som er kortere enn det vi

har. To celler forbedres:
- $d[2][4]$ : veien $2 \to 1 \to 4$ koster $8 + 7 = 15$ , mot $\infty$ før.
Forgjengeren arves fra rad 1: $\pi[2][4] = \pi[1][4] = 1$ .
- $d[4][2]$ : veien $4 \to 1 \to 2$ koster $2 + 3 = 5$ , mot $\infty$ før.
$\pi[4][2] = \pi[1][2] = 1$ .
$d^{(1)}$

1	2	3	4
1	0	3	$\infty$	7
2	8	0	2	15
3	$\infty$	$\infty$	0	1
4	2	5	$\infty$	0

c) Med

k = 2

ser vi etter stier

i \to 2 \to j

. To celler forbedres:
-

d[1][3]

: veien

1 \to 2 \to 3

koster

3 + 2 = 5

, mot

\infty

før.

$\pi[1][3] = \pi[2][3] = 2$ .
- $d[4][3]$ : veien $4 \to 2 \to 3$ koster $5 + 2 = 7$ , mot $\infty$ før.

$\pi[4][3] = \pi[2][3] = 2$ .
Sluttilstanden — det du ville levert på eksamen:
$d^{(2)}$

1	2	3	4
1	0	3	5	7
2	8	0	2	15
3	$\infty$	$\infty$	0	1
4	2	5	7	0

$\pi^{(2)}$

1	2	3	4
1	NIL	1	2	1
2	2	NIL	2	1
3	NIL	NIL	NIL	3
4	4	1	2	NIL

Legg merke til tre ting.
Alle cellene som ikke nevnes, står uendret fra forrige runde — i begge
matrisene. En vanlig feil er å regne om hele matrisen fra grunnen av.
Forgjengeren arves fra rad k, ikke fra rad i. Ved

d[4][3]

hentet vi

\pi[2][3]

, ikke

\pi[4][2]

Rad 3 er uendret gjennom begge rundene. Node 3 har bare én utgående kant, til

node 4, og hverken node 1 eller 2 kan nås derfra på to runder.
Fellen her er å blande d-regelen og π-regelen. d tar et minimum;
π gjør et valg mellom to forgjengere, og valget følger utfallet av
minimumet.

📝Oppgave 1

(Innstegsoppgave, sjanger D — definisjon med egne ord, altså én presis setning
med hovedpoenget først.)

Hva betyr $d^{(k)}_{ij}$ i Floyd-Warshall, og hva er $d^{(0)}$ ?

📝Oppgave 2

Eksamensnivå, sjanger C

Bruk grafen fra Eksempel 1, og fortsett fra $d^{(2)}$ .

Utfør runden med $k = 3$ , og oppgi bare de cellene i $d$ som endrer seg,
med de nye verdiene og de nye forgjengerne.

📝Oppgave 3

Eksamensnivå, sjanger F

Ta stilling til hver av påstandene om Floyd-Warshall:

a) Løkkene kan kjøres i hvilken som helst rekkefølge, siden alle tre går
over alle nodene.
b) Algoritmen krever ikke-negative kantvekter.
c) Kjøretiden er $\Theta(V^3)$ uansett hvor mange kanter grafen har.

`Slow-APSP` og min-pluss-produktet (~14 min)

Det finnes en helt annen vei til det samme svaret, og den er verdt å kunne
fordi den kommer som en egen håndkjøringsoppgave: å bygge stiene opp kant for
kant i stedet for mellomnode for mellomnode.

La $l^{(m)}_{ij}$ være den korteste avstanden fra $i$ til $j$ blant stier med
høyst $m$ kanter. Da er $l^{(1)} = W$ , og skrittet videre er å legge til én
kant til.

Min-pluss-produktet

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

📜Pseudokode-kontrakt: `Slow-APSP`

Antagelser om representasjon. Vektmatrisen W[1..n][1..n] som over.
L er en matrise av samme form, med L[i][j] = korteste avstand med høyst et
visst antall kanter.

Prebetingelse: ingen negativ sykel.
Postbetingelse: rutinen returnerer matrisen der hver sti er forlenget med
høyst én kant til.

Slow-APSP(L, W)
  Input:  matrisene L og W, begge n x n
  Output: matrisen L' der stiene er forlenget med hoeyst en kant
  la L' vaere en ny n x n matrise
  for i = 1 to n
      for j = 1 to n
          L'[i][j] = INF
          for k = 1 to n
              L'[i][j] = min(L'[i][j], L[i][k] + W[k][j])
  return L'
  Kjoeretid: Theta(V^3) per produkt

Invarianten i én setning: er L korteste avstander med høyst $m$ kanter,
er L' korteste avstander med høyst $m+1$ kanter.

Hele APSP-problemet løses ved å gjenta produktet. En korteste sti i en graf
uten negative sykler har høyst $V-1$ kanter, så $V-2$ produkter etter det
første holder — altså $\Theta(V^4)$ naivt. Med gjentatt kvadrering kommer man
ned i $\Theta(V^3\lg V)$ , men Floyd-Warshall med sine $\Theta(V^3)$ er
fortsatt bedre.

Kjøretid: $\Theta(V^3)$ for ett produkt, $\Theta(V^4)$ for hele den
naive løsningen.

✏️Eksempel 2: Én celle i min-pluss-produktet

Bruk den samme grafen som i Eksempel 1, med vektmatrisen $W$ .

Regn ut $l^{(2)}_{13}$ , altså den korteste avstanden fra node 1 til node 3 med
høyst to kanter. Vis alle leddene.

Vi bruker

l^{(1)} = W

og regner

$l^{(2)}_{13} = \min_{1 \le k \le 4}\left(l^{(1)}_{1k} + w_{k3}\right)$

$k$	$l^{(1)}_{1k}$	$w_{k3}$	Summen
1	$0$	$\infty$	$\infty$
2	$3$	$2$	$5$
3	$\infty$	$0$	$\infty$
4	$7$	$\infty$	$\infty$

Svaret: $l^{(2)}_{13} = 5$ , via

k = 2

, altså stien

1 \to 2 \to 3

.
Legg merke til de tre $\infty$ -leddene. Regelen

\infty + x = \infty

gjelder, og de bidrar ikke til minimumet. Leddet med

k = 1

0 + \infty

fordi det ikke finnes noen kant

1 \to 3

; leddet med

k = 4

7 + \infty

fordi det ikke finnes noen kant

4 \to 3

Kontrollen mot vanlig matriseprodukt. Med vanlig produkt ville vi regnet

$\sum_k W_{1k}\cdot W_{k3}$ , altså $0\cdot\infty + 3\cdot 2 + \infty\cdot 0 + 7\cdot\infty$ . Det gir ingen mening som avstand, og det er ikke det oppgaven
spør etter — men det er nøyaktig den feilen som gjøres når man leser
«matriseprodukt» og går på autopilot.
Svarformen på eksamen: ett tall. Ba oppgaven om hele $l^{(2)}$ , er det

matrisen. Ba den om én celle, er det tallet og ikke mer.

📝Oppgave 4

Eksamensnivå, sjanger C

Bruk grafen fra Eksempel 1.

a) Regn ut $l^{(2)}_{24}$ , altså korteste avstand fra node 2 til node 4 med
høyst to kanter.
b) Regn ut $l^{(2)}_{34}$ .

`Transitive-Closure` og utskrift av stien (~9 min)

Noen ganger er ikke avstanden interessant — bare om det i det hele tatt går an
å komme fra $i$ til $j$ . Da holder det med sanne og usanne verdier, og
algoritmen blir billigere i praksis fordi den slipper aritmetikk.

`Transitive-Closure`

t^{(k)}_{ij}

`Print-All-Pairs-Shortest-Path`

i

📝Oppgave 5

Eksamensnivå, sjanger C…

Bruk $\pi^{(2)}$ fra Eksempel 1.

a) Hvilken sti fra node 4 til node 3 er kodet i matrisen på dette
tidspunktet?
b) Forklar med én setning hvorfor d-matrisen alene ikke er nok til å
svare på a).

📝Oppgave 6

Eksamensnivå, sjanger E…

En kartleverandør skal regne ut reisetid mellom alle par av $V$ steder.

a) Grafen er glissen ( $E \approx V$ ) og alle vektene er positive. Hvilken
algoritme velger du, og hva blir kjøretiden?
b) Grafen er tett ( $E \approx V^2$ ) og noen vekter er negative, men det
finnes ingen negativ sykel. Hvilken velger du, og hva blir kjøretiden?
c) Bare spørsmålet «finnes det en vei?» skal besvares, for alle par.
Hvilken velger du?

Typiske feil

De to første koster hele oppgaven.

- Å bruke vanlig matriseprodukt i Slow-APSP. Produktet er
min-pluss: minimum av summer, ikke sum av produkter. Et svar regnet ut
med vanlig produkt er meningsløst som avstand.
- Å blande d-regelen og π-regelen. d tar et minimum; π velger
mellom den gamle forgjengeren og $\pi[k][j]$ . Og den arvede verdien hentes
fra rad k — ikke fra rad i.
- Å regne om hele matrisen i hver runde. Bare de cellene der veien om k
faktisk er kortere, endrer seg. Alle andre står uendret, i begge matrisene.
- Å bytte om løkkene i Floyd-Warshall. k må være ytterst. Med i eller
j ytterst brytes invarianten, og svaret blir galt.
- Å bruke Dijkstra på en graf med negative kanter. Dette er felle #8.
Floyd-Warshall og Bellman-Ford tåler negative kanter; Dijkstra gjør det
ikke.
- Å oppgi stien fra d-matrisen. d gir lengden, π gir veien. Ber
oppgaven om stien, skal du lese π baklengs.
- Å glemme at $\infty + x = \infty$ . I min-pluss-regningen er det de
endelige leddene som konkurrerer; $\infty$ -leddene er bare med for
fullstendighetens skyld.

Og den gjennomgående: å oppgi mer enn det som er spurt om. Ber oppgaven om
$d$ etter én bestemt runde, er det den ene matrisen som er svaret — ikke hele
kjøringen, og ikke $\pi$ i tillegg.

Kjøretidene samlet

Dette er kapitlets puggeflate. Eksamen er hjelpemiddelfri, så tabellen må ligge
i hodet.

Algoritme	Kjøretid	Krav / egenskap
`Floyd-Warshall`	$\Theta(V^3)$	tåler negative kanter; ingen negativ sykel; `k` ytterst
`Slow-APSP`, ett produkt	$\Theta(V^3)$	min-pluss, ikke vanlig matriseprodukt
`Slow-APSP`, hele problemet naivt	$\Theta(V^4)$	$V-2$ produkter etter det første
`Transitive-Closure`	$\Theta(V^3)$	boolsk: «eller» og «og» i stedet for min og pluss
`Print-All-Pairs-Shortest-Path`	$O(V)$ per sti	leser `π` baklengs
$V$ kjøringer av `Dijkstra`	$O(VE\lg V)$	krever ikke-negative vekter; best på glisne grafer
$V$ kjøringer av `Bellman-Ford`	$\Theta(V^2E)$	tåler negative kanter, men dyrt

Én presisering som er verdt å ta med seg. Floyd-Warshall bryr seg ikke om
hvor mange kanter grafen har — kjøretiden er

\Theta(V^3)

uansett. Det er både
styrken (tette grafer) og svakheten (svært glisne grafer, der

V

kjøringer av
Dijkstra er raskere).

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp
har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet
gjelder kjernestoffet.

`Floyd-Warshall`

k

`d`-regelen

d^{(k)}_{ij} = \min\left(d^{(k-1)}_{ij},\; d^{(k-1)}_{ik} + d^{(k-1)}_{kj}\right)

`π`-regelen

k

Mellomnode

d^{(k)}

Min-pluss-produktet

l^{(m)}_{ij} = \min_k\left(l^{(m-1)}_{ik} + w_{kj}\right)

`Slow-APSP`

\Theta(V^3)

l^{(m)}_{ij}

i

`Transitive-Closure`

i

`Print-All-Pairs-Shortest-Path`

\pi

Vektmatrisen

W

W[i][j] = w(i,j)

Forgjengermatrisen

\pi

\pi[i][j]

Glissen mot tett graf

E

Felle #8 — `Dijkstra` på negative kanter

Dijkstra forutsetter ikke-negative kantvekter og kan gi feil svar med én eneste negativ kant. Floyd-Warshall og Bellman-Ford tåler negative kanter. Sjekk fortegnet før du velger algoritme — det er det første spørsmålet i en korteste-vei-oppgave.

Negativ sykel

en sykel der summen av kantvektene er negativ. Da finnes ingen korteste sti: du kan gå rundt sykelen igjen og igjen og få lavere og lavere kostnad. Floyd-Warshall forutsetter at det ikke finnes noen. Bellman-Ford oppdager dem, og det er dens særegne styrke.

Sjanger C — håndkjøring

oppgavetypen der du utfører algoritmen steg for steg og oppgir sluttilstanden. Her er svarformen den etterspurte matrisen for den etterspurte runden — eller den ene cellen, hvis det er det som er spurt om. Ikke lever både d og π når bare én var etterspurt.

Sjanger E — kjøretidskunnskap

\Theta(V^3)

Repetisjonsoppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.