Sist endret: 23.09.2016  
 

Teorioppgave - Korteste vei, alle til alle

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 13.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

a) Hvilken kjøretid (asymptotisk) har Floyd-Warshall implementasjon vi finner i Cormen (s. 695)? (4 %)


b) Hvor mye plass bruker Floyd-Warshall algoritmen vi finner i Cormen (s. 695)? (4 %)


c) Kan Floyd-Warshalls algoritme brukes til å finne ut om det finnes negative sykler i en graf? (4 %)


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

Oppgave 2

Vi skal kjøre Floyd-Warshalls algoritme (slik den er beskrevet i Cormen) på følgende graf:

Gitt $D^{(0)}$:

a) Hvordan ser $D^{(1)}$ ut?


(4 %)


b) Hvordan ser $D^{(3)}$ ut?


(4 %)


c) Hvordan ser $D^{(5)}$ ut?


(4 %)


d) Hvilken sti vil Floyd-Warshall gi som korteste sti fra node 1 til node 4? (4 %)


e) Hva er tolkningen av elementet i rad $i$, kolonne $j$ i matrisen $D^{(5)}$? (4 %)


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

Oppgave 3

a) Gitt algoritmen TRANSITIVE-CLOSURE($G$) på side. 698 i Cormen. Kan vi ved hjelp av denne algoritmen finne ut om en rettet graf er asyklisk? (4 %)


b) Hvis vi endrer linje 5 i TRANSITIVE-CLOSURE($G$) til:

$\hspace{2cm} \textbf{ if } \text{ (}i,j\text{) } \text{ is in }G.E:$

Vil det nå være mulig å bruke denne algoritmen for å finne ut om en rettet graf er asyklisk?
(4 %)


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

Oppgave 4

Hva er teoretisk raskeste algoritme (best O) for "korteste vei, alle til alle" - problemet i følgende grafer?

Merk: For Dijkstras regner vi med at Extract-Min-operasjonen tar O(V) tid.

a) En rettet graf uten sykler og uten negative kanter. (8 %)


b) Assymptotisk strammeste kjøretid for de(n) raskeste algoritmen(e) i a) er? (4 %)


c) En rettet graf uten sykler og med negative kanter. (8 %)


d) Assymptotisk strammeste kjøretid for de(n) raskeste algoritmen(e) i c) er? (4 %)


e) En graf med sykler og uten negative kanter. (8 %)


f) Assymptotisk strammeste kjøretid for de(n) raskeste algoritmen(e) i e) er? (4 %)


g) En graf med sykler og med negative kanter(men uten negative sykler) (8 %)


h) Assymptotisk strammeste kjøretid for de(n) raskeste algoritmen(e) i g) er? (4 %)


i) En graf med negative sykler. Her holder det ikke å kun oppdage at det finnes negative sykler (8 %)


j) Assymptotisk strammeste kjøretid for de(n) raskeste algoritmen(e) i i) er? (4 %)


Ø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'.