eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Skolenyttig
Forum
eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Skolenyttig
Forum
eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Skolenyttig
Forum
eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Skolenyttig
Forum
Hjem
Høyskole
UiO
IN1030
Quiz
Dagens quiz – Grafalgoritmer
Dagens quiz – Grafalgoritmer
Spørsmål 1 av 10
0%
Hva er DAG korteste vei-algoritmen?
Grafalgoritmer
A
Topologisk sorter grafen, deretter relakser kanter i topologisk rekkefølge,
O
(
V
+
E
)
O(V+E)
O
(
V
+
E
)
B
Relakser alle kanter
∣
V
∣
−
1
|V|-1
∣
V
∣
−
1
ganger i vilkårlig rekkefølge,
O
(
V
⋅
E
)
O(V \cdot E)
O
(
V
⋅
E
)
C
Utforsk grafen med bredde-først-søk og oppdater avstander underveis,
O
(
V
+
E
)
O(V+E)
O
(
V
+
E
)
D
Velg som regel kanten med lavest vekt ved hjelp av en prioritetskø,
O
(
(
V
+
E
)
log
V
)
O((V+E)\log V)
O
((
V
+
E
)
lo
g
V
)
Vis hint
Rapporter feil
Dagens quiz – IN1030 | Eksamenssett