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

`Dijkstra`, `Bellman-Ford` og `DAG-Shortest-Path` — krav per algoritme (negative kanter/sykler), kjøretider og forgjengerstrukturen.

60 min

7 oppgaver

Korteste vei fra én kildeDijkstraBellman-FordDAG

Din fremgang i kapitlet

0 / 7 oppgaver

Kapitlets plass i kurset

Bygger på

4.1Grafrepresentasjon, traversering og topologisk sortering

Brukes videre i

4.4Alle-til-alle korteste vei

Du står med et vegkart, en startby og et spørsmål alle kjenner: hva er billigste
vei herfra til alle de andre? Det er hele dette kapitlet. Temaet korteste vei
fra én kilde er belagt i 13 av de 17 settene i grunnlaget (76 %), og det
kommer i tre former:

- sjanger E — kjøretidskunnskap, altså at du oppgir kjøretiden til en
navngitt algoritme som ett uttrykk, uten utregning;
- sjanger F — «stemmer dette?», altså at du svarer ja eller nei først og
så begrunner med én setning;
- sjanger C — håndkjøring, altså at du utfører algoritmen steg for steg på
papir og leverer bare sluttilstanden.

Den faste F-oppgaven i dette temaet er en variant av «kan Dijkstra brukes når
én kant har negativ vekt?». Svaret er nei, og hele kapitlet er bygget for at du
skal kunne si hvorfor på én linje.

Prioriteten er den midterste av bokas tre klasser: bør sitte. Det betyr at du
skal kunne skrive ned kravene og kjøretidene uten å slå opp — eksamen er
hjelpemiddelfri — men at du ikke trenger å kunne bevise korrektheten.

Slik er kapitlet lagt opp (60 min):

#	Innhold	Tid
1	Kantslakking: motoren i alle tre algoritmene	ca. 12 min
2	`Dijkstra` — den grådige, og kravet den stiller	ca. 15 min
3	Når `Dijkstra` går galt, og hvorfor	ca. 8 min
4	`Bellman-Ford` — den robuste	ca. 15 min
5	`DAG-Shortest-Path` — den raske når grafen er syklusfri	ca. 10 min

Forkunnskaper

- kap. 4.1 — grafrepresentasjon og traversering. Du bør
vite hva en naboliste er, og at BFS finner veien med færrest kanter —
ikke den med minst vekt. Forskjellen er hele grunnen til at dette kapitlet
finnes.
- kap. 4.1 dekker også topologisk sortering, som
DAG-Shortest-Path bygger direkte på.
- kap. 3.1 — hauger. Dijkstra bruker en prioritetskø,
og kjøretiden $O(E\lg V)$ er nettopp prisen for at prioritetskøen er en
binærhaug.
- kap. 1.1 — asymptotisk notasjon. Her skiller vi bevisst
mellom $\Theta$ (grensen er tett) og $O$ (bare øvre grense er vist).

Er logaritmen i $\lg V$ rusten, er Potenser og logaritmer et raskt
oppfriskningskapittel; $\lg n$ betyr alltid $\log_2 n$ i denne boka. Trenger du
et mykere første møte med selve $O$ -notasjonen, ligger det i
Algoritmedefinisjon, pseudokode og kompleksitet (Big-O).

Notasjons- og pseudokodeliste

Kantslakking — motoren i alle tre algoritmene (~12 min)

Tenk på en bilist som planlegger ruta si over et vegnett med bomstasjoner.
Hun har et ark med et anslag for hver by: «hit kommer jeg for høyst så mange
kroner». Anslagene starter håpløst dårlige — alle er «uendelig», bortsett fra
byen hun står i, som koster 0. Så går hun gjennom vegstrekningene én for én, og
hver gang hun ser at en strekning gir en billigere måte å nå en by på, retter hun
anslaget ned.

Det er nøyaktig det algoritmene i dette kapitlet gjør. Anslaget kalles $d[v]$ , og
operasjonen som retter det ned, kalles slakking. Alle tre algoritmene er den
samme operasjonen, kjørt i tre forskjellige rekkefølger.

Underveis noterer hun også hvor hun kom fra: hvis den billigste måten å nå $v$ på
går via $u$ , skriver hun $\pi[v] = u$ . Til slutt kan hun følge disse notatene
bakover fra en hvilken som helst by og lese ut hele ruta. Det er derfor svaret på
en korteste-vei-oppgave nesten alltid er to ting: tallene ( $d$ ) og veien
( $\pi$ ).

Korteste vei fra én kilde

O(E\lg V)

Kantslakking (*relax*)

u

d[v]

— korteste-vei-estimatet

v

\pi[v]

— forgjengeren

d[v]

✏️Eksempel 1: Én slakking, og én som ikke gjør noe

Node u har d[u] = 5. Kanten fra u til v har vekt 3.

a) v har d[v] = 11 og pi[v] = NIL. Utfør Relax(u, v, w).

b) En annen node v har d[v] = 7 og pi[v] = x. Utfør Relax(u, v, w)
med den samme kanten på 3.

a) Sporingen:

Størrelse	Før slakkingen	Test	Etter slakkingen
`d[u]`	5	uendret	5
`d[v]`	11	11 er større enn 5 + 3 = 8	8
`pi[v]`	NIL	forgjengeren settes til `u`	`u`

Sluttilstand: d[v] = 8, pi[v] = u
b) Sporingen:

Størrelse	Før slakkingen	Test	Etter slakkingen
`d[u]`	5	uendret	5
`d[v]`	7	7 er ikke større enn 5 + 3 = 8	7
`pi[v]`	`x`	ingen endring	`x`

Sluttilstand: d[v] = 7, pi[v] = x — uendret.

Poenget med b) er at $7 = 5 + 3 - 1$ ikke er større enn 8, så testen slår ikke

til. Hadde d[v] vært nøyaktig 8, hadde den heller ikke slått til: ulikheten er

streng. Det høres ut som en detalj, men det er den vanligste kilden til at to
studenter får ulik $\pi$ -struktur på det samme eksempeloppgavesettet.

📝Oppgave 1

(Innstegsoppgave, sjanger C — håndkjøring, altså at du utfører operasjonen steg
for steg og oppgir bare sluttilstanden.) Tre noder har d[u] = 4, d[v] = 12 og
d[x] = 20, og pi[u] = s mens pi[v] og pi[x] er NIL. Utfør disse tre
slakkingene i rekkefølge:

a) Relax(u, v, w) med w(u,v) = 5
b) Relax(u, x, w) med w(u,x) = 9
c) Relax(v, x, w) med w(v,x) = 3

Oppgi d og pi for alle tre nodene til slutt. Oppgaven ber om verdiene, ikke
om en forklaring av hva slakking er.

`Dijkstra` — den grådige, og kravet den stiller (~15 min)

Tilbake til bilisten. Den smarteste måten å jobbe seg gjennom kartet på, er å ta
byene i rekkefølge etter hvor billige de er: den nærmeste først, så den nest
nærmeste, og så videre. Når hun har funnet den aller billigste byen som ennå ikke
er behandlet, kan hun låse anslaget for den — ingen senere oppdagelse kan
gjøre den billigere.

Det er Dijkstra. Algoritmen holder alle ubehandlede noder i en prioritetskø
sortert på $d$ , plukker ut den minste med Extract-Min, låser den, og slakker
alle kantene ut fra den. Så gjentar den til køen er tom.

Men se på argumentet for låsingen én gang til: «ingen senere oppdagelse kan gjøre
den billigere». Det holder bare hvis det å gå en omvei alltid koster mer.
Med en negativ kantvekt kan en omvei koste mindre — og da faller hele resonnementet.
Det er derfor Dijkstra krever ikke-negative kantvekter, og det er den viktigste
enkeltsetningen i dette kapitlet.

`Dijkstra`

d

Prioritetskø

d[v]

📜Pseudokode-kontrakt: `Dijkstra`

Antagelser om representasjon. Grafen

G=(V,E)

er rettet og gitt som
nabolister, slik at kantene ut fra en node kan gjennomløpes i tid proporsjonalt
med antallet. Hver node v har feltene v.d og v.pi. Vektfunksjonen w
oppgir vekten på hver kant. Q er en prioritetskø på v.d, i praksis en
binærhaug.

Prebetingelse: alle kantvekter er ikke-negative, w(u,v) >= 0.
Postbetingelse: for hver node v er v.d lik vekten til en korteste vei fra
s til v, og v.pi peker på forgjengeren på en slik vei. Noder som ikke er
nåbare fra s, står igjen med v.d = uendelig.

Dijkstra(G, w, s)
  Input:  graf G = (V, E) med ikke-negative vekter w, kilde s
  Output: v.d og v.pi for hver node v i V
  Initialize-Single-Source(G, s)
  S = tom mengde
  Q = alle noder i V, med noekkel v.d
  while Q er ikke tom
      u = Extract-Min(Q)
      legg u til S
      for hver kant (u, v) ut fra u
          Relax(u, v, w)

Initialize-Single-Source(G, s)
  for hver node v i V
      v.d = uendelig
      v.pi = NIL
  s.d = 0

Relax(u, v, w)
  if v.d > u.d + w(u, v)
      v.d = u.d + w(u, v)
      v.pi = u

Grunnideen i én setning: når en node tas ut av Q, er den den nærmeste av
alle som gjenstår, og siden ingen kant kan trekke fra noe underveis, finnes det
ingen vei rundt som kan bli billigere — altså er u.d endelig i det øyeblikket.

Kjøretid: $O(E\lg V)$ . Hver node tas ut av køen nøyaktig én gang, altså $V$
kall på Extract-Min à $O(\lg V)$ ; hver kant slakkes nøyaktig én gang, altså
opptil $E$ kall på Decrease-Key à $O(\lg V)$ . Summen $O((V+E)\lg V)$ skrives
$O(E\lg V)$ når grafen er sammenhengende, siden $E \ge V-1$ da. Merk at det er
$O$ , ikke $\Theta$ : antallet vellykkede Decrease-Key-kall avhenger av grafen.

✏️Eksempel 2: `Dijkstra` på et bomvegnett

Seks kryss i et vegnett heter S, A, B, C, D og E. Strekningene er
enveiskjørte, og tallet på hver strekning er bomavgiften i kroner:

S -> A  4      B -> A   1      C -> D  2
S -> B  2      B -> C   8      C -> E  6
A -> C  5      B -> D  10      D -> E  3

Kjør Dijkstra fra S. Oppgi v.d for hver node.

Prioritetskøen plukker alltid den ubehandlede noden med minst d. Er to like,
tas den som kommer først alfabetisk.

Sporingstavlen. Hver rad er ett Extract-Min pluss slakkingen av alle kantene
ut fra noden som ble plukket:

Steg	`Extract-Min` gir	`d` for noden	Slakking av kantene ut	`d` etter steget
1	`S`	0	(S,A): 0 + 4 = 4 < $\infty$ , d[A] = 4, pi[A] = S; (S,B): 0 + 2 = 2 < $\infty$ , d[B] = 2, pi[B] = S	S: 0, A: 4, B: 2, C: $\infty$ , D: $\infty$ , E: $\infty$
2	`B`	2	(B,A): 2 + 1 = 3 < 4, d[A] = 3, pi[A] = B; (B,C): 2 + 8 = 10 < $\infty$ , d[C] = 10, pi[C] = B; (B,D): 2 + 10 = 12 < $\infty$ , d[D] = 12, pi[D] = B	S: 0, A: 3, B: 2, C: 10, D: 12, E: $\infty$
3	`A`	3	(A,C): 3 + 5 = 8 < 10, d[C] = 8, pi[C] = A	S: 0, A: 3, B: 2, C: 8, D: 12, E: $\infty$
4	`C`	8	(C,D): 8 + 2 = 10 < 12, d[D] = 10, pi[D] = C; (C,E): 8 + 6 = 14 < $\infty$ , d[E] = 14, pi[E] = C	S: 0, A: 3, B: 2, C: 8, D: 10, E: 14
5	`D`	10	(D,E): 10 + 3 = 13 < 14, d[E] = 13, pi[E] = D	S: 0, A: 3, B: 2, C: 8, D: 10, E: 13
6	`E`	13	ingen kanter ut	S: 0, A: 3, B: 2, C: 8, D: 10, E: 13

Nodene ble låst i rekkefølgen S, B, A, C, D, E — altså
stigende etter d, som seg hør og bør for en grådig algoritme.
På eksamen leverer du bare linja under — tavlen er her for å vise hvordan du
kommer dit.
v.d: S: 0, A: 3, B: 2, C: 8, D: 10, E: 13
Forgjengerne, hvis oppgaven også ber om dem: S: NIL, A: B, B: S, C: A, D: C, E: D
Legg merke til steg 2 og 3: A fikk først d = 4 direkte fra S, men ble

senket til 3 da B ble behandlet. Det er lov — A var ikke tatt ut av køen
ennå. Etter at en node ER tatt ut, skjer det aldri mer.

Fellenote. Fellen her er å stoppe før køen er tom, eller å låse A med 4 i
det øyeblikket den fikk sin første verdi. En d-verdi er ikke endelig før noden

er plukket av Extract-Min.

📝Oppgave 2

Eksamensnivå, sjanger E

a) Hva er kjøretiden til Dijkstra når prioritetskøen er en binærhaug?
b) Begrunn den i én setning ved å telle operasjonene på prioritetskøen.
c) Hvorfor skriver vi

O

og ikke

\Theta

her?

Når `Dijkstra` går galt (~8 min)

— naturlig pausepunkt —

La oss se hva som faktisk skjer med en negativ kant. Et ferjeselskap gir rabatt
på en bestemt overfart hvis du har kjøpt billett på en annen strekning først. I
grafen blir den rabatterte overfarten en kant med negativ vekt: du betaler
mindre samlet enn du gjorde før du tok den.

Nå er antakelsen som Dijkstra hviler på, brutt. Algoritmen låser en node fordi
«ingen omvei kan bli billigere» — men en omvei innom den rabatterte kanten kan
være akkurat det.

✏️Eksempel 3: `Dijkstra` svarer feil på fire noder

Grafen har fire noder og fire kanter:

S -> A   2
S -> B   3
B -> A  -2
A -> C   1

a) Kjør Dijkstra fra S mekanisk, uten å «reparere» noe, og oppgi v.d.
b) Hva er den sanne korteste veien til C?

a) Sporingen, kjørt mekanisk:

Steg	`Extract-Min` gir	`d` for noden	Slakking av kantene ut	`d` etter steget
1	`S`	0	(S,A): 0 + 2 = 2 < $\infty$ , d[A] = 2, pi[A] = S; (S,B): 0 + 3 = 3 < $\infty$ , d[B] = 3, pi[B] = S	S: 0, A: 2, B: 3, C: $\infty$
2	`A`	2	(A,C): 2 + 1 = 3 < $\infty$ , d[C] = 3, pi[C] = A	S: 0, A: 2, B: 3, C: 3
3	`B`	3	(B,A): 3 + -2 = 1 < 2, d[A] = 1, pi[A] = B	S: 0, A: 1, B: 3, C: 3
4	`C`	3	ingen kanter ut	S: 0, A: 1, B: 3, C: 3

Nodene ble låst i rekkefølgen S, A, B, C.
Dijkstra svarer: S: 0, A: 1, B: 3, C: 3
b) Den sanne korteste veien til C går S, B, A, C og koster

3 + (-2) + 1 = 2

. Kjørt med Bellman-Ford, som tåler negative kanter, blir
fasiten: S: 0, A: 1, B: 3, C: 2

Avviket: Dijkstra svarer d[C] = 3; korrekt korteste vei er 2.

Hvor gikk det galt? I steg 2 ble A tatt ut av køen med d[A] = 2 og låst.

Kanten fra A til C ble slakket med den verdien, så d[C] ble 3. Først i
steg 3 oppdaget algoritmen at A egentlig kunne nås for 1 via B — men da var
A allerede behandlet, og Dijkstra går aldri tilbake til en behandlet node.

Forbedringen av d[A] rakk aldri fram til C.

Merk en viktig nyanse. Dijkstra svarer ikke alltid feil når det finnes en
negativ kant; på mange grafer kommer den heldigvis i mål. Men den gir ingen
garanti, og på eksamen er det garantien som spørres etter. Riktig svar er derfor
alltid: nei, Dijkstra kan ikke brukes — bruk Bellman-Ford.

Typiske feil

Fire feil koster mest i dette kapitlet.

- Å bruke Dijkstra på en graf med negativ kantvekt. Dette er felle #8 —
å bruke Dijkstra på negative kantvekter, når algoritmen krever at alle
kantvekter er ikke-negative. Eksempel 3 viser hva som faktisk skjer. Rett svar
på «kan Dijkstra brukes her?» når minst én kant er negativ, er nei, med
begrunnelsen at en behandlet node aldri revurderes.
- *Å tro at Bellman-Ford bare finner negative sykler. Den håndterer
dem: kontrollrunden etter de $V-1$ slakkerundene får algoritmen til å returnere
USANN, som er det riktige svaret — for da finnes det ingen korteste vei å
oppgi. En «vei» kan gå rundt sykelen så mange ganger den vil og bli vilkårlig
billig.
- Å oppgi feil kjøretid for Dijkstra. Riktig er $O(E\lg V)$ med binærhaug.
$O(V^2\lg V)$ er ikke det strammeste uttrykket, og $\Theta(V+E)$ er ren
forveksling med BFS.
- Å kjøre DAG-Shortest-Path på en graf med sykel. Da finnes det ingen
topologisk orden, og algoritmen er ikke definert. Sjekk alltid at grafen
faktisk er syklusfri før du bruker den.

Og den stille: å stoppe håndkjøringen for tidlig.* En d-verdi er ikke
endelig i Dijkstra før noden er plukket av Extract-Min, og ikke endelig i
Bellman-Ford før alle $V-1$ rundene er kjørt.

📝Oppgave 3

Eksamensnivå, sjanger F

a) En rettet graf har 40 kanter. 39 av dem har positiv vekt, én har vekten

-1

. Kan Dijkstra brukes til å finne korteste vei fra en kilde s?
b) Samme graf: kan Bellman-Ford brukes?
c) Stemmer det at Dijkstra alltid gir feil svar når grafen har en negativ
kant?

`Bellman-Ford` — den robuste (~15 min)

Når du ikke kan stole på rekkefølgen, dropper du rekkefølgen. Bellman-Ford
slakker rett og slett alle kantene i grafen, om og om igjen, $V-1$ ganger.

Hvorfor akkurat $V-1$ ? Fordi en korteste vei aldri kan ha flere enn $V-1$ kanter
— hadde den hatt flere, ville den besøkt en node to ganger, altså gått i en
sykel, og en sykel med positiv vekt kan alltid klippes bort. Etter runde 1 er
alle korteste veier med én kant funnet, etter runde 2 alle med to kanter, og så
videre.

Og der Dijkstra bare feiler stille på en negativ sykel, gjør Bellman-Ford det
eneste ærlige: den kjører én runde til. Hvis en eneste kant fortsatt kan
slakkes etter $V-1$ runder, finnes det en negativ sykel nåbar fra kilden, og da
returnerer algoritmen USANN. Det er riktig svar, for da finnes det ingen korteste
vei: du kan gå rundt sykelen så mange ganger du vil og få vilkårlig lav vekt.

`Bellman-Ford`

V-1

Negativ sykel

V-1

Tidlig stopp i `Bellman-Ford`

d

📜Pseudokode-kontrakt: `Bellman-Ford`

Antagelser om representasjon. Grafen

G=(V,E)

er rettet og gitt som en
kantliste, siden algoritmen uansett skal gjennom alle kanter hver runde.
Rekkefølgen på kantlista er fast og oppgitt. Hver node v har feltene v.d og
v.pi.

Prebetingelse: ingen — vektene kan være negative.
Postbetingelse: hvis ingen negativ sykel er nåbar fra s, returneres SANN,
og v.d er vekten til en korteste vei fra s til v for hver node. Finnes det
en negativ sykel nåbar fra s, returneres USANN, og v.d-verdiene er
meningsløse.

Bellman-Ford(G, w, s)
  Input:  graf G = (V, E) som kantliste, vekter w (kan vaere negative), kilde s
  Output: SANN med v.d og v.pi satt, eller USANN ved negativ sykel naabar fra s
  Initialize-Single-Source(G, s)
  for i = 1 to |V| - 1
      for hver kant (u, v) i E, i den faste rekkefoelgen
          Relax(u, v, w)
  for hver kant (u, v) i E
      if v.d > u.d + w(u, v)
          return USANN
  return SANN

Invarianten i én setning: etter runde $i$ er v.d korrekt for alle noder
v som har en korteste vei fra s med høyst $i$ kanter.

Kjøretid: $\Theta(VE)$ . Den ytre for-løkka går $V-1$ ganger, den indre gjennom
alle $E$ kanter, og hver slakking er $\Theta(1)$ ; kontrollrunden legger til
$\Theta(E)$ , som forsvinner i det største leddet. Her står det $\Theta$ og ikke
$O$ : uten tidlig stopp gjøres arbeidet uansett hva grafen ser ut som.

✏️Eksempel 4: `Bellman-Ford` på et ferjenett med rabatt

Fem havner heter S, A, B, C og D. Tallene er prisen i hundrelapper for
hver overfart; to av dem er negative fordi selskapet gir rabatt når du allerede
har kjøpt en tidligere billett i kjeden:

S -> A   4      A -> B  -1      C -> D   2
S -> B   6      A -> C   3      D -> A   8
B -> C  -2      B -> D   5

Kantene skal slakkes i denne faste rekkefølgen hver runde:

(D,A), (C,D), (B,D), (B,C), (A,C), (A,B), (S,B), (S,A)

Kjør Bellman-Ford fra S. Oppgi v.d for hver node, og si om algoritmen
returnerer SANN eller USANN.

Grafen har 5 noder, så det kjøres $5 - 1 = 4$ runder. Sporingstavlen har én rad
per kant per runde:

Runde	Kant	Vekt	Test `d[v] > d[u] + w(u,v)`?	Resultat	`d` etter steget
1	`(D,A)`	8	d[D] er $\infty$	ingen endring	S: 0, A: $\infty$ , B: $\infty$ , C: $\infty$ , D: $\infty$
1	`(C,D)`	2	d[C] er $\infty$	ingen endring	S: 0, A: $\infty$ , B: $\infty$ , C: $\infty$ , D: $\infty$
1	`(B,D)`	5	d[B] er $\infty$	ingen endring	S: 0, A: $\infty$ , B: $\infty$ , C: $\infty$ , D: $\infty$
1	`(B,C)`	-2	d[B] er $\infty$	ingen endring	S: 0, A: $\infty$ , B: $\infty$ , C: $\infty$ , D: $\infty$
1	`(A,C)`	3	d[A] er $\infty$	ingen endring	S: 0, A: $\infty$ , B: $\infty$ , C: $\infty$ , D: $\infty$
1	`(A,B)`	-1	d[A] er $\infty$	ingen endring	S: 0, A: $\infty$ , B: $\infty$ , C: $\infty$ , D: $\infty$
1	`(S,B)`	6	0 + 6 = 6 er mindre enn $\infty$	d[B] = 6, pi[B] = S	S: 0, A: $\infty$ , B: 6, C: $\infty$ , D: $\infty$
1	`(S,A)`	4	0 + 4 = 4 er mindre enn $\infty$	d[A] = 4, pi[A] = S	S: 0, A: 4, B: 6, C: $\infty$ , D: $\infty$
2	`(D,A)`	8	d[D] er $\infty$	ingen endring	S: 0, A: 4, B: 6, C: $\infty$ , D: $\infty$
2	`(C,D)`	2	d[C] er $\infty$	ingen endring	S: 0, A: 4, B: 6, C: $\infty$ , D: $\infty$
2	`(B,D)`	5	6 + 5 = 11 er mindre enn $\infty$	d[D] = 11, pi[D] = B	S: 0, A: 4, B: 6, C: $\infty$ , D: 11
2	`(B,C)`	-2	6 + (-2) = 4 er mindre enn $\infty$	d[C] = 4, pi[C] = B	S: 0, A: 4, B: 6, C: 4, D: 11
2	`(A,C)`	3	4 + 3 = 7 er ikke mindre enn 4	ingen endring	S: 0, A: 4, B: 6, C: 4, D: 11
2	`(A,B)`	-1	4 + (-1) = 3 er mindre enn 6	d[B] = 3, pi[B] = A	S: 0, A: 4, B: 3, C: 4, D: 11
2	`(S,B)`	6	0 + 6 = 6 er ikke mindre enn 3	ingen endring	S: 0, A: 4, B: 3, C: 4, D: 11
2	`(S,A)`	4	0 + 4 = 4 er ikke mindre enn 4	ingen endring	S: 0, A: 4, B: 3, C: 4, D: 11
3	`(D,A)`	8	11 + 8 = 19 er ikke mindre enn 4	ingen endring	S: 0, A: 4, B: 3, C: 4, D: 11
3	`(C,D)`	2	4 + 2 = 6 er mindre enn 11	d[D] = 6, pi[D] = C	S: 0, A: 4, B: 3, C: 4, D: 6
3	`(B,D)`	5	3 + 5 = 8 er ikke mindre enn 6	ingen endring	S: 0, A: 4, B: 3, C: 4, D: 6
3	`(B,C)`	-2	3 + (-2) = 1 er mindre enn 4	d[C] = 1, pi[C] = B	S: 0, A: 4, B: 3, C: 1, D: 6
3	`(A,C)`	3	4 + 3 = 7 er ikke mindre enn 1	ingen endring	S: 0, A: 4, B: 3, C: 1, D: 6
3	`(A,B)`	-1	4 + (-1) = 3 er ikke mindre enn 3	ingen endring	S: 0, A: 4, B: 3, C: 1, D: 6
3	`(S,B)`	6	0 + 6 = 6 er ikke mindre enn 3	ingen endring	S: 0, A: 4, B: 3, C: 1, D: 6
3	`(S,A)`	4	0 + 4 = 4 er ikke mindre enn 4	ingen endring	S: 0, A: 4, B: 3, C: 1, D: 6
4	`(D,A)`	8	6 + 8 = 14 er ikke mindre enn 4	ingen endring	S: 0, A: 4, B: 3, C: 1, D: 6
4	`(C,D)`	2	1 + 2 = 3 er mindre enn 6	d[D] = 3, pi[D] = C	S: 0, A: 4, B: 3, C: 1, D: 3
4	`(B,D)`	5	3 + 5 = 8 er ikke mindre enn 3	ingen endring	S: 0, A: 4, B: 3, C: 1, D: 3
4	`(B,C)`	-2	3 + (-2) = 1 er ikke mindre enn 1	ingen endring	S: 0, A: 4, B: 3, C: 1, D: 3
4	`(A,C)`	3	4 + 3 = 7 er ikke mindre enn 1	ingen endring	S: 0, A: 4, B: 3, C: 1, D: 3
4	`(A,B)`	-1	4 + (-1) = 3 er ikke mindre enn 3	ingen endring	S: 0, A: 4, B: 3, C: 1, D: 3
4	`(S,B)`	6	0 + 6 = 6 er ikke mindre enn 3	ingen endring	S: 0, A: 4, B: 3, C: 1, D: 3
4	`(S,A)`	4	0 + 4 = 4 er ikke mindre enn 4	ingen endring	S: 0, A: 4, B: 3, C: 1, D: 3

Antall vellykkede slakkinger per runde: runde 1: 2 endringer, runde 2: 3 endringer, runde 3: 2 endringer, runde 4: 1 endringer. Legg
merke til at det skjedde en endring helt til og med runde 4 — den ugunstige
kantrekkefølgen gjør at forbedringene forplanter seg bare ett hakk per runde.
Hadde kantene ligget i motsatt rekkefølge, hadde alt vært på plass etter runde 1.
Kontrollrunden: ingen kant kan slakkes mer, altså ingen negativ sykel nåbar fra S Algoritmen returnerer SANN.
På eksamen leverer du bare linja under — tavlen er her for å vise hvordan du
kommer dit.
v.d: S: 0, A: 4, B: 3, C: 1, D: 3
Forgjengerne: S: NIL, A: S, B: A, C: B, D: C
Fellenote. Fellen her er å stoppe etter runde 1 fordi «det ser ferdig ut».
Det gjorde det ikke: D gikk fra 11 via 6 til 3 gjennom rundene 2, 3 og 4.
Oppgaven ber om verdiene etter at algoritmen er ferdig, ikke etter første runde.

📝Oppgave 4

Eksamensnivå, sjanger C

En rettet graf har nodene S, A, B
og C og kantene

A -> C   2
C -> B  -4
S -> A   6
S -> B   7
B -> A   3

Kantene slakkes i nøyaktig den rekkefølgen de står i lista over, i hver runde.
Kjør Bellman-Ford fra S.

a) Hva er d for hver node etter runde 1?
b) Hva er d for hver node når algoritmen er ferdig?
c) Returnerer algoritmen SANN eller USANN?

Oppgaven ber om verdiene, ikke om en forklaring av algoritmen.

📝Oppgave 5

Eksamensnivå, sjanger C…

En rettet graf har nodene S, X,
Y og Z og kantene

S -> X   4
X -> Y   3
Y -> Z  -2
Z -> X  -3
X -> Z   9

Kantene slakkes i den rekkefølgen de står, i hver runde.

a) Kjør Bellman-Ford fra S og oppgi hvilken kant som fortsatt kan slakkes
i kontrollrunden.
b) Hva returnerer algoritmen, og hva betyr det for spørsmålet «hva er
korteste vei fra S til Z?»

`DAG-Shortest-Path` — den raske når grafen er syklusfri (~10 min)

— naturlig pausepunkt —

Et monteringsverksted setter sammen et produkt i en fast rekkefølge: kabinettet
må stå før kortet kan settes inn, kortet før lokket kan skrus på. Noen
delmontasjer kan gjøres i parallell, men ingen operasjon kan komme etter seg
selv. En slik graf har ingen sykler — den er en rettet asyklisk graf, på
engelsk directed acyclic graph, forkortet DAG.

I en DAG kan du sortere nodene i en lineær topologisk orden, der hver kant
peker framover. Og da trenger du verken prioritetskø eller gjentatte runder: gå
gjennom nodene i topologisk orden og slakk kantene ut fra hver av dem, én gang.
Når du kommer til en node, er alle veiene inn til den allerede ferdigbehandlet.

Det gir $\Theta(V+E)$ — raskere enn både Dijkstra og Bellman-Ford — og
algoritmen tåler negative kantvekter uten videre, siden det uansett ikke finnes
noen sykel å gå rundt.

Rettet asyklisk graf (DAG)

En rettet graf uten sykler: det finnes ingen vei som starter og ender i den samme noden. Navnet kommer fra engelsk, directed acyclic graph . Modellen passer på alt som har en «må gjøres før»-struktur: monteringsrekkefølger, emneforløp, oppgaver med avhengigheter. Nøkkelegenskapen er at nodene kan legges i en topologisk orden. Har grafen bare én eneste sykel, finnes ingen slik orden, og DAG-Shortest-Path kan ikke brukes.

Topologisk orden

u

`DAG-Shortest-Path`

d

📜Pseudokode-kontrakt: `DAG-Shortest-Path`

Antagelser om representasjon. Grafen

G=(V,E)

er rettet, asyklisk og
gitt som nabolister. Hver node v har feltene v.d og v.pi. Vektene kan være
negative.

Prebetingelse: G har ingen sykler. Postbetingelse: v.d er vekten til
en korteste vei fra s til v for hver node v, og v.pi gir veien bakover.
Noder som ikke er nåbare fra s, står igjen med v.d = uendelig.

DAG-Shortest-Path(G, w, s)
  Input:  rettet asyklisk graf G = (V, E), vekter w, kilde s
  Output: v.d og v.pi for hver node v i V
  sorter nodene i V topologisk
  Initialize-Single-Source(G, s)
  for hver node u i V, i topologisk orden
      for hver kant (u, v) ut fra u
          Relax(u, v, w)

Invarianten i én setning: når den ytre for-løkka kommer til node u, er
u.d allerede ferdig, fordi hver kant inn til u går fra en node som står
tidligere i den topologiske ordenen og derfor allerede er behandlet.

Kjøretid: $\Theta(V+E)$ . Den topologiske sorteringen er $\Theta(V+E)$ ,
initialiseringen $\Theta(V)$ , og den doble løkka ser på hver kant nøyaktig én
gang, altså $\Theta(E)$ . Her er $\Theta$ riktig: arbeidet gjøres uansett hvordan
DAG-en ser ut.

✏️Eksempel 5: `DAG-Shortest-Path` på en monteringslinje

Seks operasjoner heter A til F. En kant fra X til Y betyr at X må
gjøres før Y, og vekten er omstillingstiden i minutter — negativ der to
operasjoner deler samme oppsett og verkstedet sparer tid:

A -> B   5      C -> D   7      D -> F   2
A -> C   3      C -> E   4      E -> F  -1
B -> C  -2      D -> E   1

En topologisk orden er A, B, C, D, E, F. Kjør DAG-Shortest-Path fra
A og oppgi v.d for hver node.

Sporingen, én rad per node i topologisk orden:

Steg	Node i topologisk orden	`d` for noden	Slakking av kantene ut	`d` etter steget
1	`A`	0	(A,B): 0 + 5 = 5 < $\infty$ , d[B] = 5, pi[B] = A; (A,C): 0 + 3 = 3 < $\infty$ , d[C] = 3, pi[C] = A	A: 0, B: 5, C: 3, D: $\infty$ , E: $\infty$ , F: $\infty$
2	`B`	5	(B,C): 5 + (-2) = 3 ikke mindre enn 3, ingen endring; (B,D): 5 + 6 = 11 < $\infty$ , d[D] = 11, pi[D] = B	A: 0, B: 5, C: 3, D: 11, E: $\infty$ , F: $\infty$
3	`C`	3	(C,D): 3 + 7 = 10 < 11, d[D] = 10, pi[D] = C; (C,E): 3 + 4 = 7 < $\infty$ , d[E] = 7, pi[E] = C	A: 0, B: 5, C: 3, D: 10, E: 7, F: $\infty$
4	`D`	10	(D,E): 10 + 1 = 11 ikke mindre enn 7, ingen endring; (D,F): 10 + 2 = 12 < $\infty$ , d[F] = 12, pi[F] = D	A: 0, B: 5, C: 3, D: 10, E: 7, F: 12
5	`E`	7	(E,F): 7 + (-1) = 6 < 12, d[F] = 6, pi[F] = E	A: 0, B: 5, C: 3, D: 10, E: 7, F: 6
6	`F`	6	ingen kanter ut	A: 0, B: 5, C: 3, D: 10, E: 7, F: 6

På eksamen leverer du bare linja under — tavlen er her for å vise hvordan du
kommer dit.
v.d: A: 0, B: 5, C: 3, D: 10, E: 7, F: 6
Forgjengerne: A: NIL, B: A, C: A, D: C, E: C, F: E
To ting er verdt å legge merke til. I steg 2 ble kanten fra B til C slakket
uten at noe skjedde:

5 + (-2) = 3

, og d[C] var allerede 3. Ulikheten er
streng, så pi[C] ble stående på A. Og i steg 5 senket den negative kanten

d[F] fra 12 til 6 — helt uproblematisk, fordi grafen ikke har noen sykel å gå
rundt.

Fellenote. Fellen her er å behandle nodene i alfabetisk rekkefølge i stedet

for topologisk. Med denne grafen ville det gitt samme svar tilfeldigvis, men det

gjør det ikke generelt: hele garantien hviler på at ingen kant peker bakover.

📝Oppgave 6

Eksamensnivå, sjanger C

En rettet asyklisk graf har nodene S,
P, Q, R og T, og kantene

S -> P   3      P -> R   6      Q -> T   9
S -> Q   8      Q -> R   1      R -> T   2
P -> Q  -2

En topologisk orden er S, P, Q, R, T. Kjør DAG-Shortest-Path fra S
og oppgi v.d for hver node.

📝Oppgave 7

Eksamensnivå, sjanger F…

For hver av de fire situasjonene: si
hvilken av Dijkstra, Bellman-Ford og DAG-Shortest-Path du ville brukt, og
oppgi kjøretiden til valget ditt. Velg den raskeste algoritmen som faktisk
kan brukes.

a) Et vegnett med bomavgifter. Alle avgifter er positive, grafen har sykler.
b) En monteringsplan der noen omstillinger sparer tid (negative vekter), og
ingen operasjon kan komme etter seg selv.
c) Et rutenett der to strekninger gir rabatt (negative vekter) og det finnes
sykler.
d) Samme graf som i c), men du skal i tillegg avgjøre om det i det hele tatt
finnes en korteste vei.

Hvilken algoritme når? (~5 min)

Alle tre løser det samme problemet og bruker den samme slakkeregelen. Det som
skiller dem, er hva de krever av grafen — og prisen du betaler for robustheten.

Algoritme	Beste tilfelle	Verste tilfelle	Krav og egenskap
`Dijkstra` (binærhaug)	$\Omega(E + V\lg V)$	$O(E\lg V)$	krever ikke-negative kantvekter; grådig, låser én node per runde
`Bellman-Ford`	$\Theta(V+E)$ med tidlig stopp	$\Theta(VE)$	tåler negative kanter; oppdager negative sykler nåbare fra kilden
`DAG-Shortest-Path`	$\Theta(V+E)$	$\Theta(V+E)$	krever DAG; tåler negative vekter, raskest av de tre
`BFS` (til sammenligning)	$\Theta(V+E)$	$\Theta(V+E)$	gir færrest kanter, ikke minst vekt — bare riktig når alle vekter er like

Les tabellen nedenfra og opp når du skal velge: er grafen syklusfri, ta den
øverste raden du har lov til. Er den ikke det, avgjør fortegnene på vektene.
Én ting til som gjelder alle tre: er en node ikke nåbar fra kilden, står

d

igjen
på

\infty

. Det er et gyldig svar, ikke en feil.

Begrepsbank

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

Forgjengertreet

(\pi[v], v)

Trekantulikheten for korteste veier

v

Vektfunksjonen

w(u,v)

u

Nåbar fra kilden

v

`Extract-Min` og `Decrease-Key`

d

Binærhaug som prioritetskø

\lfloor i/2\rfloor

Grådig algoritme

\Theta(VE)

Korteste vei som ikke finnes

d[v]

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.

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

Forkunnskaper

Kantslakking — motoren i alle tre algoritmene (~12 min)

Dijkstra — den grådige, og kravet den stiller (~15 min)

Når Dijkstra går galt (~8 min)

Bellman-Ford — den robuste (~15 min)

DAG-Shortest-Path — den raske når grafen er syklusfri (~10 min)

Hvilken algoritme når? (~5 min)

Begrepsbank

`Dijkstra` — den grådige, og kravet den stiller (~15 min)

Når `Dijkstra` går galt (~8 min)

`Bellman-Ford` — den robuste (~15 min)

`DAG-Shortest-Path` — den raske når grafen er syklusfri (~10 min)