Sist endret: 23.09.2016  
 

Løsningsforslag - Korteste vei, alle til alle

[Oppgave] [Levering] [Løsningsforslag]

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

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

$O(V^2E)$
$O(V^3)$
$\Theta(V^3)$
$\Theta(E^3)$

Din kommentar:
LF-forklaring:

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

$\Theta(1)$
$\Theta(V)$
$\Theta(V^2)$
$\Theta(V^3)$

Din kommentar:
LF-forklaring:

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

Ja
Nei

Din kommentar:
LF-forklaring:

Oppgave 2

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

Gitt $D^{(0)}$:

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


(4 %)

a)
b)
c)
d)

Din kommentar:
LF-forklaring:

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


(4 %)

a)
b)
c)
d)

Din kommentar:
LF-forklaring:

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


(4 %)

a)
b)
c)
d)

Din kommentar:
LF-forklaring:

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

1-2-5-4
1-2-3-1-2-3-5-4
1-2-3-5-4
1-2-4

Din kommentar:
LF-forklaring:

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

Korteste vei fra i til j som ikke bruker mer enn 5 kanter
Korteste vei fra i til j som ikke går igjennom mer enn 5 noder
Korteste vei fra i til j som får lov til å gå igjennom node 1, 2, 3, 4 og 5
Matrisen er kun et ledd i utregningen, og elementene har ingen videre betydning

Din kommentar:
LF-forklaring:

Oppgave 3

[ riktig ]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 %)

Ja
Nei

Din kommentar:
LF-forklaring:

[ riktig ]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 %)

Ja
Nei

Din kommentar:
LF-forklaring:

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.

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

Dijkstra, kjørt V ganger
Dag-Shortest-path, kjørt V ganger
Floyd-Warshall
Bellman-Ford, kjørt V ganger
Ingen av de nevnte kan løse problemet (uten modifikasjoner)
Ingen er entydig best

Din kommentar:
LF-forklaring:

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

O(1)
O(EV+V2)
O(VlgE)
O(VlgV)
O(V2+VElgE)
O(VE+V2+lgV)
O(EV2)
O(VE2)
O(V2)
O(E3)
O(V3)
Ingen kunne løse problemet

Din kommentar:
LF-forklaring:

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

Dijkstra, kjørt V ganger
Dag-Shortest-path, kjørt V ganger
Floyd-Warshall
Bellman-Ford, kjørt V ganger
Ingen av de nevnte kan løse problemet (uten modifikasjoner)
Ingen er entydig best

Din kommentar:
LF-forklaring:

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

O(1)
O(EV+V2)
O(VlgE)
O(VlgV)
O(V2+VElgE)
O(VE+V2+lgV)
O(EV2)
O(VE2)
O(V2)
O(E3)
O(V3)
Ingen kunne løse problemet

Din kommentar:
LF-forklaring:

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

Dijkstra, kjørt V ganger
Dag-Shortest-path, kjørt V ganger
Floyd-Warshall
Bellman-Ford, kjørt V ganger
Ingen av de nevnte kan løse problemet (uten modifikasjoner)
Ingen er entydig best

Din kommentar:
LF-forklaring: Både Floyd-Warshall og Dijkstras har O(V^3)

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

O(1)
O(EV+V2)
O(VlgE)
O(VlgV)
O(V2+VElgE)
O(VE+V2+lgV)
O(EV2)
O(VE2)
O(V2)
O(E3)
O(V3)
Ingen kunne løse problemet

Din kommentar:
LF-forklaring:

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

Dijkstra, kjørt V ganger
Dag-Shortest-path, kjørt V ganger
Floyd-Warshall
Bellman-Ford, kjørt V ganger
Ingen av de nevnte kan løse problemet (uten modifikasjoner)
Ingen er entydig best

Din kommentar:
LF-forklaring:

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

O(1)
O(EV+V2)
O(VlgE)
O(VlgV)
O(V2+VElgE)
O(VE+V2+lgV)
O(EV2)
O(VE2)
O(V2)
O(E3)
O(V3)
Ingen kunne løse problemet

Din kommentar:
LF-forklaring:

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

Dijkstra, kjørt V ganger
Dag-Shortest-path, kjørt V ganger
Floyd-Warshall
Bellman-Ford, kjørt V ganger
Ingen av de nevnte kan løse problemet (uten modifikasjoner)
Ingen er entydig best

Din kommentar:
LF-forklaring:

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

O(1)
O(EV+V2)
O(VlgE)
O(VlgV)
O(V2+VElgE)
O(VE+V2+lgV)
O(EV2)
O(VE2)
O(V2)
O(E3)
O(V3)
Ingen kunne løse problemet

Din kommentar:
LF-forklaring: