eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Privatundervisning
Kontakt
eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Privatundervisning
Kontakt
eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Privatundervisning
Kontakt
eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Privatundervisning
Kontakt
Hjem
Høyskole
NTNU
TDT4120
Quiz
Dagens quiz – Grafalgoritmer
Dagens quiz – Grafalgoritmer
Spørsmål 1 av 10
0%
Hva bruker man for korteste vei i en DAG?
Grafalgoritmer
A
d
i
j
(
k
)
=
min
(
d
i
j
(
k
−
1
)
,
d
i
k
(
k
−
1
)
+
d
k
j
(
k
−
1
)
)
d_{ij}^{(k)} = \min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)})
d
ij
(
k
)
=
min
(
d
ij
(
k
−
1
)
,
d
ik
(
k
−
1
)
+
d
kj
(
k
−
1
)
)
B
All-pairs SP med blanding av Bellman-Ford og Dijkstra —
O
(
V
2
log
V
+
V
E
)
O(V^2 \log V + VE)
O
(
V
2
lo
g
V
+
V
E
)
C
Topologisk sortering etterfulgt av relaksering i topologisk rekkefølge:
O
(
V
+
E
)
O(V+E)
O
(
V
+
E
)
D
For tette grafer (
E
≈
V
2
E \approx V^2
E
≈
V
2
) eller når man trenger
O
(
1
)
O(1)
O
(
1
)
kantoppslag
Vis hint
Rapporter feil