Sist endret: 23.09.2016  
 

Teorioppgave - Korteste vei, én til alle

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 06.11.2017 15:00

NB! Du er ikke innlogget. Logg inn for å få frem det du har skrevet tidligere.
Dersom du har levert øvingen fra før, vil det du har levert bli slettet dersom du klikker på 'Vis alternativer'

NB! Det du skriver i tekstfeltene blir ikke vurdert som en del av besvarelsen. De er kun til eget bruk, før du velger 'Vis alternativer'.

Oppgave 1

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

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


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 %)


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


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 %)


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 %)


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


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 %)


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 %)


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 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

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.

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


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


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


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


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


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


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


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


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


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


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


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 3

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

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


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


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


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


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

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.

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


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


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


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


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


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


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 %)


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


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


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Stikkord til forelesning

Du får mer utbytte av en forelesning dersom du på forhånd vet helt overfladisk hva den handler om. Du bør ane hva stikkordene for neste forelesning betyr.
Skriv gjerne ned kommentarer til stikkordene for neste forelesning og se over dem på neste teoriøving.

Kommentarer til stikkordene er kun til eget bruk og blir ikke vurdert av andre.

Det er ikke lagt inn noen stikkord for neste forelesning.


Eventuelt tidligere innlevering vil bli OVERSKREVET om du klikker på 'Vis alternativer'.