Sist endret: 23.09.2016  
 
Øvinger
 
Blackboard
Piazza
 
IDI
NTNU
 
haakowar logget inn
Poengoversikt

Løsningsforslag - Korteste vei, én til alle

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 06.11.2017 15:00

Du er logget inn og får derfor se om du har svart riktig/feil på de enkelte oppgavene.
LF-svar er markert med grønt og feil svar er markert med rødt.

Hvis dere er uenige i fasit, oppfordres dere til å diskutere dette på Piazza.

Oppgave 1

Denne opppgaven handler om korteste vei, én til alle. Se innledning til kapittel 24.

[ riktig ]a) Hva går korteste vei-problemet ut på? (1.9 %)

Finne stier fra noder til andre noder som minimerer summen av kantvektene
Finne stien med den kanten som har lavest kantvekt
Finne sykler med færrest mulig kanter

Din kommentar:
LF-forklaring:

[ riktig ]b) Hvis man vet hvordan man finner korteste en-til-alle veier kan man også finne korteste alle-til-en veier. Sant eller usant? (1.9 %)

Sant
Usant

Din kommentar:
LF-forklaring: Ved å snu alle kantene kan man redusere alle-til-en til en-til-alle.

[ feil ]c) Korteste vei har optimal substruktur. Sant eller usant? (1.9 %)

Sant
Usant

Din kommentar:
LF-forklaring:

[ riktig ]d) Hvis man har korteste vei fra node A til B og korteste vei fra node B til C så kan man sette sammen disse to for å få korteste vei fra A til C. Sant eller usant? (1.9 %)

Sant
Usant

Din kommentar:
LF-forklaring: Selv om korteste vei har optimal substruktur betyr det ikke at vi kan sette sammento vilkårlige optimale løsninger. Optimal substruktur sier bare at den optimale løsningen består av optimale løsninger på delproblemer, men sier ingenting om hvilke delproblemer. Det er ikke sikkert den optimale løsningen går via B.

[ riktig ]e) Hvis man har funnet korteste vei fra A til C, og denne veien går innom B, har vi også funnet korteste fra vei fra A til B og fra B til C. Sant eller usant? (1.9 %)

Sant
Usant

Din kommentar:
LF-forklaring: Optimal substruktur

[ feil ]f) Hvilken algoritme egner seg best til å finne korteste vei i en urettet graf der alle kantvekter er 7? (1.9 %)

DFS
BFS
Dijkstra
Bellman-Ford
Prim
Kruskal

Din kommentar:
LF-forklaring:

[ feil ]g) Hvis en graf har negative sykler kan man øke kantvekten på alle kanter like mye slik at syklene blir positive og finne korteste med noen av algoritmene fra pensum. Sant eller usant? (1.9 %)

Sant
Usant

Din kommentar:
LF-forklaring:

[ riktig ]h) Vi har $u.d = 3, v.d = 8, w(u,v) = 2$. Hva blir $u.d$ og $v.d$ etter $RELAX(u, v, w)$? (1.9 %)

$u.d=3, v.d=5$
$u.d=3, v.d=6$
$u.d=3, v.d=7$
$u.d=3, v.d=10$
$u.d=1, v.d=8$
$u.d=2, v.d=8$
$u.d=3, v.d=8$
$u.d=5, v.d=8$

Din kommentar:
LF-forklaring:

[ riktig ]i) Vi har $u.d = 5, v.d = 7, w(u,v) = 4$. Hva blir $u.d$ og $v.d$ etter $RELAX(u, v, w)$? (1.9 %)

$u.d=5, v.d=3$
$u.d=5, v.d=4$
$u.d=5, v.d=7$
$u.d=5, v.d=11$
$u.d=1, v.d=7$
$u.d=4, v.d=7$
$u.d=9, v.d=7$
$u.d=1, v.d=3$

Din kommentar:
LF-forklaring:

Oppgave 2

Denne oppgaven handler om Bellman-Ford. Se kapittel 24.1.



I denne oppgaven skal vi bruke denne grafen. Vi skal finne korteste vei fra node F. For dette skal vi bruke Bellman-Ford (se side 651).

Når du utfører Bellman-Ford skal du iterere over kanter i alfabetisk rekkefølge. Der kanten fra A til B heter AB og kanten fra F til C heter FC.

[ feil ]a) Etter linje 1 i algoritmen - hva er $F.d$? (1.9 %)

0
1
2
3
4
5
6
7
8
9
$\infty$

Din kommentar:
LF-forklaring:

[ riktig ]b) Etter linje 1 i algoritmen - hva er $A.d$? (1.9 %)

0
1
2
3
4
5
6
7
8
9
$\infty$

Din kommentar:
LF-forklaring:

[ feil ]c) Etter én iterasjon av for-løkken på linje 2-4 - hva er $B.d$? (3.8 %)

0
1
2
3
4
5
6
7
8
9
$\infty$

Din kommentar:
LF-forklaring:

[ feil ]d) Etter én iterasjon av for-løkken på linje 2-4 - hva er $C.d$? (3.8 %)

0
1
2
3
4
5
6
7
8
9
$\infty$

Din kommentar:
LF-forklaring:

[ feil ]e) Etter én iterasjon av for-løkken på linje 2-4 - hva er $D.d$? (3.8 %)

0
1
2
3
4
5
6
7
8
9
$\infty$

Din kommentar:
LF-forklaring:

[ feil ]f) Etter to iterasjoner av for-løkken på linje 2-4 - hva er $B.d$? (3.8 %)

0
1
2
3
4
5
6
7
8
9
$\infty$

Din kommentar:
LF-forklaring:

[ feil ]g) Etter to iterasjoner av for-løkken på linje 2-4 - hva er $C.d$? (3.8 %)

0
1
2
3
4
5
6
7
8
9
$\infty$

Din kommentar:
LF-forklaring:

[ feil ]h) Etter to iterasjoner av for-løkken på linje 2-4 - hva er $D.d$? (3.8 %)

0
1
2
3
4
5
6
7
8
9
$\infty$

Din kommentar:
LF-forklaring:

[ riktig ]i) Bellman-Ford fungerer med negative kanter (men ingen negative sykler). Sant eller usant? (1.9 %)

Sant
Usant

Din kommentar:
LF-forklaring:

[ riktig ]j) Bellman-Ford oppdager negative sykler. Sant eller usant? (1.9 %)

Sant
Usant

Din kommentar:
LF-forklaring:

[ riktig ]k) Hva er kjøretiden til Bellman-Ford? (1.9 %)

$\theta(V^2)$
$\theta(EV)$
$\theta((E+V)lgV)$
$\theta(E^2)$

Din kommentar:
LF-forklaring:

Oppgave 3

Denne oppgaven handler om DAG shortest path. Se kapittel 24.2.

[ feil ]a) Kan vi bruke DAG shortest path på grafen i Bellman-Ford-oppgaven over? (1.9 %)

Ja, men kjøretiden blir ikke optimal
Ja, det vil være optimalt
Nei, grafen inneholder en sykel
Nei, grafen har ingen negative kanter

Din kommentar:
LF-forklaring:

[ riktig ]b) Vi kan bruke DAG shortest path med negative kanter. Sant eller usant? (1.9 %)

Sant
Usant

Din kommentar:
LF-forklaring:

[ feil ]c) Hvor mange ganger kjører vi $RELAX$ på hver kant? (1.9 %)

1
$V$
$E$
$V+E$

Din kommentar:
LF-forklaring:

[ riktig ]d) Hva er kjøretiden til DAG shortest path? (1.9 %)

$\theta(V + E)$
$\theta(VE)$
$\theta(V)$
$\theta(E)$

Din kommentar:
LF-forklaring:

Oppgave 4

Denne oppgaven handler om Dijkstra. Se kapittel 24.3.



I denne oppgaven skal vi bruke denne grafen. Vi skal finne korteste vei fra node F. For dette skal vi bruke Dijkstra (se side 658).

Hvis du kan velge mellom to noder velger du i alfabetisk rekkefølge.

[ feil ]a) I hvilken rekkefølge legges nodene til i S? (11.4 %)

ABCDEF
ABEFCD
CADEBF
CADEFB
FABEDC
FADEBC
FAEDCB
FCDABE
FCDAEB
FEABCD
FEABDC
FEACDB

Din kommentar:
LF-forklaring:

[ feil ]b) Hva er $C.d$ etter én iterasjon av while-løkken på linje 4-8? (3.8 %)

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

Din kommentar:
LF-forklaring:

[ feil ]c) Hva er $C.d$ etter to iterasjoner av while-løkken på linje 4-8? (3.8 %)

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

Din kommentar:
LF-forklaring:

[ feil ]d) Hva er $C.d$ etter tre iterasjoner av while-løkken på linje 4-8? (3.8 %)

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

Din kommentar:
LF-forklaring:

[ feil ]e) Hva er $C.d$ etter fire iterasjoner av while-løkken på linje 4-8? (3.8 %)

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

Din kommentar:
LF-forklaring:

[ feil ]f) Hva er $C.d$ etter fem iterasjoner av while-løkken på linje 4-8? (3.8 %)

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

Din kommentar:
LF-forklaring:

[ feil ]g) For å få Dijkstra til å fungere med negative kanter kan man legge på en konstant på alle kantervekter slik at alle kantvektene blir positive og deretter kjøre Dijkstra. Sant eller usant? (1.9 %)

Sant
Usant

Din kommentar:
LF-forklaring: Dette kan endre på hvilken sti som er kortest fordi stier med flere kanter får økt lengden sin mer enn stier med færre kanter.

[ riktig ]h) Dijkstra er en grådig algoritme. Sant eller usant? (1.9 %)

Sant
Usant

Din kommentar:
LF-forklaring: Dijkstra sitt grådige valg er å hele tiden velge noden med lavest øvre grense.

[ feil ]i) På hvilken måte beviser boka Dijkstra sin korrekthet? (Teorem 24.6 på side 659) (7.6 %)

Viser at vi kjører $RELAX$ i rekkefølge over korteste sti
Viser at vi kjører $RELAX$ $V-1$ ganger på hver kant
Viser at avstandsestimatet til nodene alltid går nedover
Viser at neste node som velges til enhver tid har riktig avstandsestimat

Din kommentar:
LF-forklaring: