6.5 DRILL — Korteste-vei-matrisen og MST-modellering

Drill på sjanger F (korteste-avstander-matrisen, kjøretid per grafalgoritme) og H (MST-modellering, reversert Dijkstra) — velg alltid lavest kjøretid.

85 min

12 oppgaver

DRILLKorteste-vei-matrisenMST-modellering

Din fremgang i kapitlet

0 / 12 oppgaver

Kapitlets plass i kurset

Bygger på

6.4Huffman-koding

Brukes videre i

6.PPrøver til del 6: Korteste vei, spenntrær og grådighet

Dette er drillkapitlet for hele Del 6, og det trener tre sjangre samtidig:

- Sjanger F — matriseavkryssing, altså at du kobler graftype til algoritme.
Denne kommer i 4 av 7 sett, og den er blant de sikreste Del 1-poengene som
finnes. Korteste-vei-matrisen og kjøretidstabellen er de to faste variantene.
- Sjanger H — grafalgoritme i pseudokode, altså at du gjenkjenner problemet,
skriver algoritmen og oppgir kjøretiden. Her ligger modelleringen: «koble
billigst», «nærmeste kilde», «hvilken rekkefølge».
- Sjanger E — håndkjøring, altså at du utfører algoritmen steg for steg og
oppgir sluttilstanden. Huffman er den vanligste håndkjøringen fra Del 6.

Prioritet: høyeste for matrisen (den kommer, og den er ren poengsanking),
kunne for modelleringen (nivå 2 — den avgjør A mot B, ikke bestått).

Slik er kapitlet lagt opp (85 min): løsningsoppskrift, ett gjennomkjørt
eksamenscase med sensor-margnotater, og deretter tolv oppgaver på eksamensnivå.
Regn med rundt 7 minutter per oppgave, og ta gjerne kapitlet over to økter — det er
et naturlig pausepunkt etter oppgave 6.

Sist du var her — forkunnskaper i kortform

Fire resultater fra Del 6 brukes i hver eneste oppgave her. De står ferdig
oppfrisket:

1. Korteste-avstander-matrisen. Uvektet gir BFS; vektet DAG gir topologisk
sortering; ingen negative kanter gir Dijkstra; negative kanter uten negativ sykel
gir Bellman-Ford. Se kap. 6.2.

2. Kjøretidene, som må sitte hjelpemiddelfritt.

Algoritme	Kjøretid
BFS, DFS-full, topologisk sortering, DAG-korteste-vei	$O(\lvert V \rvert + \lvert E \rvert)$
Dijkstra og Prim med binær prioritetskø	$O((\lvert V \rvert + \lvert E \rvert)\log \lvert V \rvert)$
Kruskal	$O(\lvert E \rvert \log \lvert E \rvert)$
Bellman-Ford	$O(\lvert V \rvert \cdot \lvert E \rvert)$
Huffman	$O(n \log n)$ , $n$ = antall symboler

3. BFS og DFS finner ikke minimale spenntrær. De leser ikke kantvektene i det
hele tatt. Se kap. 6.3.
4. Reversert Dijkstra. Flere mulige utgangspunkt og ett mål: snu grafen, kjør
én Dijkstra fra målet. Se kap. 6.2.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften — tre spørsmål og en poengtrapp

Alle oppgavene i Del 6 kan angripes med den samme faste framgangsmåten.

Steg 1 — hva slags problem er dette? Les oppgaveteksten og finn signalordene:

Ser du …	Er problemet …	Bruk
«raskest fram», «korteste rute», «minst tid»	korteste vei	BFS / topsort / Dijkstra / Bellman-Ford
«koble alt sammen billigst», «minst mulig graving totalt»	minimalt spenntre	Prim eller Kruskal
«må gjøres før», «avhengigheter», «sirkulær»	topologisk sortering	Kahn
«hvilket av flere utgangspunkt er nærmest»	korteste vei, reversert	én Dijkstra i $G^R$
«korteste vei i det ferdige nettet»	traversering i et tre	BFS eller DFS
«kort kode til vanlige tegn», «færrest bits»	optimal prefikskode	Huffman

Steg 2 — hvilken variant? For korteste vei: still de to spørsmålene i
rekkefølge. Har grafen vekter? Er den asyklisk? Finnes en negativ kant? Velg den
øverste raden i matrisen som passer.
Steg 3 — skriv svaret i fire ledd. Dette er sensors faktiske krav, og mangler
ett av dem, trekkes det:
1. Navngi problemet — «dette er et minimalt spenntre».
2. Oppgi antagelser om representasjon — nabolister, kantliste, hvilke felt en

node har.
3. Algoritmen — pseudokode eller en klar forklaring i naturlig språk. Begge
gir full uttelling; kravet er at svaret er entydig, ikke at det er syntaks.

4. Kjøretid som matcher algoritmen du faktisk ga, med $|V|$ og $|E|$ definert —
og én setning om hvorfor dette er lavest mulig.

Poengtrappen, som ligger under alt: «lavere kjøretidskompleksitet er mer
poenggivende». På samme oppgave gir $O(|V| + |E|)$ full pott,
$O((|V| + |E|)\log |V|)$ mindre, og $O(|V| \cdot |E|)$ eller
$O(|U| \cdot (|V| + |E|)\log |V|)$ minst. Å velge riktig algoritme er å velge
poeng.

✏️Eksempel 1: Gjennomkjørt eksamenscase med sensor-margnotater

Et sensornettverk har seks målestasjoner. Meldinger sendes langs faste,
enveiskjørte radiolenker, og hver lenke har en forsinkelse i millisekunder:
A -> B 6, A -> C 1, C -> B 2, C -> D 5, B -> D 3, B -> E 9,
D -> E 2, D -> F 7, E -> F 1.

a) Hvor lang tid tar det før en melding fra $A$ når hver av de andre
stasjonene? Oppgi algoritme og kjøretid.

b) Stasjonene skal i tillegg kobles sammen med kabel. Alle par kan kobles, og
hver kabelstrekning har en kjent anleggspris. Hvilket problem er det, og hvilken
algoritme velger du?

c) En kollega foreslår å bruke Bellman-Ford i deloppgave a), «for sikkerhets
skyld». Hva blir konsekvensen?

a) Steg 1 — hva slags problem? «Hvor lang tid tar det» og «fra

A

» er
signalordene for korteste vei fra én kilde.

Sensor-margnotat: å navngi problemet er hovedmomentet, og det gir mest av alt.
En besvarelse som starter med å skrive kode uten å si hva problemet er, mister
typisk et helt poeng selv om koden er riktig.

Steg 2 — hvilken variant? Kantene har vekter, så BFS er ute. Grafen har ingen
negative vekter, og selv om alle kantene her går «framover» alfabetisk, sier ikke
oppgaven noe om at nettet er asyklisk — radiolenker kan gå begge veier i andre
oppsett. Vi velger derfor Dijkstra, som er raden «ingen negative kanter».

Sensor-margnotat: hadde oppgaven eksplisitt sagt at grafen er en DAG, ville
topologisk sortering vært det øverste trinnet i trappen ( $O(|V| + |E|)$ ) og
Dijkstra gitt noe mindre. Les oppgaveteksten svært nøye — det er det mest
gjentatte rådet i hele arkivet.

Steg 3 — svaret i fire ledd.

Problemet navngitt: korteste vei fra én kilde i en rettet, vektet graf med
ikke-negative vekter.

Antagelser om representasjon: grafen $G = (V, E)$ er gitt som nabolister, der
G.naboer(v) gir parene (w, vekt). Prioritetskøen er en binær min-heap med
RemoveMin og DecreaseKey i $O(\log |V|)$ .

Algoritmen: Dijkstra. Kjøringen på tallene:

Steg	Ferdig (tatt ut av køen)	Relakserte kanter	avstand-tabell etter	Prioritetskø etter (heap-array)
1	A (avstand 0)	`B: ∞ -> 6`, `C: ∞ -> 1`	`A=0, B=6, C=1, D=∞, E=∞, F=∞`	`(1, C), (∞, F), (6, B), (∞, D), (∞, E)`
2	C (avstand 1)	`B: 6 -> 3`, `D: ∞ -> 6`	`A=0, B=3, C=1, D=6, E=∞, F=∞`	`(3, B), (6, D), (∞, E), (∞, F)`
3	B (avstand 3)	`E: ∞ -> 12`	`A=0, B=3, C=1, D=6, E=12, F=∞`	`(6, D), (∞, F), (12, E)`
4	D (avstand 6)	`E: 12 -> 8`, `F: ∞ -> 13`	`A=0, B=3, C=1, D=6, E=8, F=13`	`(8, E), (13, F)`
5	E (avstand 8)	`F: 13 -> 9`	`A=0, B=3, C=1, D=6, E=8, F=9`	`(9, F)`
6	F (avstand 9)	ingen	`A=0, B=3, C=1, D=6, E=8, F=9`	`tom`

Sluttilstand:

A=0, B=3, C=1, D=6, E=8, F=9

Kjøretid:

O((|V| + |E|)\log |V|)

, der

|V| = 6

er antall målestasjoner og

|E| = 9

er antall radiolenker.

|V|

uttak fra prioritetskøen à

O(\log |V|)

,
pluss opptil

|E|

DecreaseKey à

O(\log |V|)

Sensor-margnotat: kjøretiden må matche algoritmen du faktisk ga. Skriver du
Dijkstra og oppgir $O(|V| + |E|)$ , trekkes det — ikke fordi tallet er lavt, men
fordi det er feil for koden din.

Merk hva som skjedde med $B$ . Den direkte lenken A -> B tar 6 ms, men veien

via $C$ tar $1 + 2 = 3$ . I steg 2 senkes avstanden, og forgjenger[B] blir $C$ .
Og se på $F$ : først 13 via $D$ , så 9 via $E$ . Den nest siste relakseringen avgjorde
svaret.

b) Steg 1 — hva slags problem? «Kobles sammen» og «anleggspris» er signalordene
for et minimalt spenntre. Vekten er en kostnad ved å ha kabelen, ikke ved å
bruke den.

Algoritmen: Prim med binær prioritetskø. Siden alle par kan kobles, er grafen
komplett, og $|E| = |V|(|V|-1)/2$ . Kjøretiden blir da $O(|V|^2 \log |V|)$ .

Sensor-margnotat: «alle par kan kobles» er et signal som er verdt et halvt
poeng i seg selv — det er invitasjonen til å oppgi kjøretiden i
$O(|V|^2 \log |V|)$ -form. Kruskal med $O(|E| \log |E|)$ er like riktig.

Merk at dette er et helt annet problem enn a), på det samme nodesettet.
Korteste vei minimerer avstander fra én node; MST minimerer summen av kantene. Å

levere Dijkstra på b) er blant de dyreste enkeltfeilene i Del 6.
c) Bellman-Ford gir riktig svar, men koster $O(|V| \cdot |E|)$ i stedet for

$O((|V| + |E|)\log |V|)$ . Det er en tregere algoritme på et problem der en raskere
finnes, og poengtrappen straffer det direkte: typisk full pott for Dijkstra, klart
mindre for Bellman-Ford, på samme oppgave.

Sensor-margnotat: «for sikkerhets skyld» er aldri en god strategi i dette
faget. Den tregeste korrekte algoritmen er nesten alltid den som gir færrest
poeng. Bruk heller ti sekunder på å stille de to spørsmålene i matrisen.

Typiske feil

Feilkatalogen for Del 6, samlet. Alle er hentet fra bokas feilregister:

- Felle #1 — full gjennomgang der ett grep holdt. Å kjøre Dijkstra fra hvert
utgangspunkt i stedet for én kjøring i den reverserte grafen. Koster typisk halve
poengsummen på Del 2.
- Dijkstra på en graf med en negativ kant. Kravet er at ingen kant er
negativ. «Ingen negativ sykel» er Bellman-Fords krav — å blande dem er den
dyreste enkeltfeilen i Del 6.
- BFS eller DFS som MST-algoritme. De leser ikke kantvektene. Fast
avkryssingsfelle på sjanger F.
- Dijkstra i et ferdig spenntre. Der finnes bare én vei mellom to noder, og
vektene er byggekostnader. Bruk BFS eller DFS, $O(|V|)$ .
- Å oppgi en kjøretid som ikke matcher algoritmen. Det trekkes for manglende
kjøretid, for feil kjøretid, og for å bruke $n$ uten å si hva $n$ er (felle
#10).
- Å ikke melde fra om sykel i en topologisk sortering. Sammenlign alltid
lengden på rekkefølgen med $|V|$ .
- Å gi kortest Huffman-kode til det sjeldneste symbolet. Kontrollen: sorter
etter frekvens og sjekk at kodelengdene går motsatt vei.
- Å levere et spenntre med feil antall kanter. Nøyaktig $|V| - 1$ , alltid.

Tolv oppgaver på eksamensnivå

Oppgavene roterer de tre sjangrene: matriseavkryssing (F), håndkjøring (E) og
modellering i pseudokode (H). Alle har full fasit med poengfordeling. Ta dem på
tid — rundt 7 minutter hver.

📝Oppgave 1

(Innstegsoppgave, sjanger F — matriseavkryssing, altså at du kobler graftype til
algoritme.) Fyll inn den raskeste korrekte algoritmen og dens kjøretid i hver rad.

Grafen er …	Algoritme	Kjøretid
uvektet	?	?
vektet DAG	?	?
vektet, ingen negative kanter	?	?
vektet med negative kanter, ingen negativ sykel	?	?

📝Oppgave 2

Sjanger F

Fyll inn kjøretiden for hver grafalgoritme, med binær prioritetskø
der det er relevant.

a) Full dybde-først-traversering (DFS-full)
b) Topologisk sortering med Kahns algoritme
c) Prims algoritme
d) Bellman-Ford
e) Kruskals algoritme

📝Oppgave 3

Sjanger F

Sett kryss for hver algoritme: finner den et minimalt spenntre?

a) Prim
b) Bredde-først-søk
c) Kruskal
d) Dijkstra
e) Borůvka
f) Dybde-først-søk

📝Oppgave 4

Sjanger E

En urettet vektet graf har kantene $A$ – $B$ 5, $A$ – $C$ 9,
$B$ – $C$ 3, $B$ – $D$ 8, $C$ – $D$ 2, $C$ – $E$ 7, $D$ – $E$ 4, $D$ – $F$ 6, $E$ – $F$ 1.

a) Kjør Prim fra $A$ . Oppgi kantene i treet og totalvekten.
b) Kontrollér antall kanter.
c) Hvilke kanter ble aldri med, og hvorfor ikke?

📝Oppgave 5

Sjanger E

Kjør Kruskals algoritme på den samme grafen som i oppgave 4:
$A$ – $B$ 5, $A$ – $C$ 9, $B$ – $C$ 3, $B$ – $D$ 8, $C$ – $D$ 2, $C$ – $E$ 7, $D$ – $E$ 4,
$D$ – $F$ 6, $E$ – $F$ 1.

a) Sett opp kantene i sortert rekkefølge.
b) Vis kjøringen med union-find-tilstanden underveis.
c) Sammenlign med Prim-svaret fra oppgave 4.

📝Oppgave 6

Sjanger E

Fem statuskoder har frekvensene $K$ 11, $L$ 7, $M$ 5, $N$ 3, $O$ 2.

a) Bygg Huffman-treet og oppgi kodelengden per symbol.
b) Hvor mange bits trengs totalt?
c) Hvor mye spares mot en fast koding?

— naturlig pausepunkt —

De seks første oppgavene var Del 1-stoff: avkryssinger og håndkjøringer. De seks
siste er Del 2 — modellering i pseudokode, der karakteren avgjøres. Ta dem gjerne
i en egen økt, og gi deg selv 8 til 10 minutter per oppgave.

📝Oppgave 7

Sjanger H

Et bibliotek av programmoduler har
avhengighetene A -> C, B -> C, C -> D, C -> E, D -> F, E -> F,
F -> G, B -> E.

a) Hvilket problem er dette, og hvilken algoritme velger du?
b) Håndkjør algoritmen og oppgi rekkefølgen.
c) Skriv algoritmen i pseudokode, med kjøretid.

📝Oppgave 8

Sjanger H

En vektet DAG har kantene A -> B 2, A -> C 6, B -> C 3,
B -> D 9, C -> D 1, C -> E 4, D -> F 2, E -> F 5.

a) Hvilken algoritme gir korteste vei fra $A$ med lavest kjøretid, og hvorfor?
b) Kjør den og oppgi avstandstabellen.
c) Hva ville Dijkstra kostet på samme graf?

📝Oppgave 9

Sjanger H

Et distribusjonsnett har fire lagre og ett mottak $T$ . Reisetidene er
enveiskjørte: P -> C 5, Q -> C 8, Q -> D 2, R -> D 4, C -> T 3,
D -> T 6.

a) Hvilket lager er nærmest $T$ ? Vis hvordan du finner det med én
algoritmekjøring.
b) Oppgi kjøretiden, og sammenlign med den naive løsningen.
c) Hvorfor gir metoden også svaret for lagre som legges til senere?

📝Oppgave 10

Sjanger H

Etter at spenntreet fra oppgave 4 er bygget — kantene $A$ – $B$ ,
$B$ – $C$ , $C$ – $D$ , $D$ – $E$ , $E$ – $F$ — skal en tekniker gå fra $A$ til $F$
gjennom nettet.

a) Hvilken algoritme velger du, og hvorfor ikke Dijkstra?
b) Kjør den og oppgi antall strekk fra $A$ til hver node.
c) Hva blir kjøretiden, uttrykt i $|V|$ ?

📝Oppgave 11

Sjanger H, krevende

En kommune har $|V|$ adressepunkter og $|E|$ mulige
grøfter, hver med en gravekostnad. De vil ha svar på tre ting:

a) Billigste nett som kobler alle adressene sammen.
b) Hvilken av tre mulige sentraler som ligger nærmest en bestemt adresse, målt
i kjøretid langs veinettet (en annen graf, med reisetider).
c) Om et sett med rekkefølgekrav for gravearbeidet lar seg gjennomføre.

For hver deloppgave: navngi problemet, oppgi algoritme og kjøretid, og si hva den
naive løsningen ville kostet.

📝Oppgave 12

Sjanger H, krevende

En kollega leverer denne besvarelsen på oppgaven «finn
korteste reisetid fra depotet til alle utsalgssteder i et veinett med
enveiskjøring og positive reisetider»:

«Jeg bruker Bellman-Ford. Den relakserer alle kantene $n$ ganger og gir korteste
vei. Kjøretiden er $O(n^2)$ .»

a) Hva er riktig ved besvarelsen?
b) Finn de tre problemene med den.
c) Skriv en besvarelse som ville fått full uttelling.

Begrepsbank

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

Korteste-vei-matrisen på ti sekunder

Still to spørsmål: har grafen vekter, og er den asyklisk? Ingen vekter gir BFS. Asyklisk gir topologisk sortering. Ellers: ingen negativ kant gir Dijkstra, negativ kant gir Bellman-Ford. Velg alltid den øverste raden som passer — den er raskest.

Kjøretidstabellen for grafalgoritmer

O(|V| + |E|)

Signalordene i Del 6

«Raskest fram» gir korteste vei. «Koble alt sammen billigst» gir minimalt spenntre. «Må gjøres før» gir topologisk sortering. «Hvilket av flere utgangspunkt» gir reversert Dijkstra. «Korteste vei i det ferdige nettet» gir BFS eller DFS. «Færrest bits» gir Huffman. Halve jobben på Del 2 er å kjenne igjen mønsteret; resten er å skrive ned algoritmen du allerede kan.

Del 2-svarformen — fire ledd

|V|

Poengtrappen

O(|V| + |E|)

Felle #1 i grafdelen

Full eller naiv gjennomgang der ett grep holdt: Dijkstra fra hvert utgangspunkt i stedet for én kjøring i den reverserte grafen, eller søk fra hver node i stedet for én SCC-kjøring. Koster typisk halve poengsummen på Del 2, og det er dokumentert som A/B-skillet på korteste-vei-oppgaver.

Kontrollregningene i Del 6

|V| - 1

To grafer over de samme punktene

En eksamensoppgave gir ofte to helt forskjellige grafer over det samme nodesettet: én med anleggskostnader (som gir et spenntreproblem) og én med reisetider (som gir et korteste-vei-problem). Spørsmålet som skiller dem: måler vekten en kostnad ved å ha kanten, eller ved å bruke den?

Prim og Dijkstra er samme algoritme med én linje forskjell

O((|V| + |E|)\log |V|)

Hva sensor faktisk trekker for

n

Repetisjon — Del 6 på ett kort

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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.