29
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU x y 2 4 9 5 8 5 6 10 8 1 3 9 7 2 4 4 start cíl Chceme najít nejkratší cestu z vrcholu x do vrcholu y.
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
x
y
2
4
9
5
8
5
6
108 1 3
9
7
2
4
4
start
cíl
Chceme najít nejkratší cestu z vrcholu x do vrcholu y.
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
x
y
2
4
5
6
108 1 3
9
7
2
4
4start
cíl
Chceme najít nejkratší cestu z vrcholu x do vrcholu y.
8
5
9
4 + 8 + 5 + 9 = 26
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
x
y
2
4
5
6
10 1 3
7
2
4
4start
cíl
Chceme najít nejkratší cestu z vrcholu x do vrcholu y.
8
5
9
4 + 8 + 5 + 9 = 26
8
98 + 9 = 17
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
Edsger Wybe Dijkstra (1930 – 2002), nizozemský informatik
Odkaz na demonstrační video
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
Do každého vcholu zapíšeme délku nejkratší cesty z x – na začátku, kdy délky cest neznáme je to krom vrcholu x
x0
c
a
d
e
b
y
2
4
9
5
8
5
6
108 1 3
9
f
7
2
4
4
start
cíl
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c
a
d
e
b
y
2
4
9
5
8
5
6
108 1 3
9
f
7
2
4
4
start
cíl
Nyní odebereme vrchol s nejmenší hodnotou
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c
a
d
e
b
y
2
4
9
5
8
5
6
108 1 3
9
f
7
2
4
4
start
cíl
Nyní odebereme vrchol s nejmenší hodnotou
x0
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d
e,8
b
y
2
4
9
5
8
5
6
108 1 3
9
f
7
2
4
4
start
cíl
a nastavíme vzdálenosti do vrcholů, do nichž vedou hrany z odebraného vrcholu
x0
x0
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,x2
a,4
d
e,8
b
y
2
4
9
5
8
5
6
108 1 3
9
f
7
2
4
4
start
cíl
odebereme vrchol s nejmenší hodnotou
x0
x0
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,x2
a,4
d,7
e,8
b
y
2
4
9
5
8
5
6
108 1 3
9
f
7
2
4
4
start
cíl
nahradíme hodnoty ve vrcholech spojenýcg hranou s odebraným hodnotou cesty z x, pokud je menší než nastavená
x0
c,x2
x0
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,x4
d,7
e,8
b
y
2
4
9
5
8
5
6
108 1 3
9
f
7
2
4
4
start
cíl
odebereme vrchol s nejmenší hodnotou
x0
c,x2
x0
c,x2
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,8
b
y
2
4
9
5
8
5
6
108 1 3
9
f
7
2
4
4
start
cíl
odebereme vrchol s nejmenší hodnotou
a
x0
c,x2
a,x4
c,x2
x0
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,8
b,12
y
2
4
9
5
8
5
6
108 1 3
9
f
7
2
4
4
start
cíl
a
x0
nahradíme hodnoty ve vrcholech spojených hranou s odebraným hodnotou cesty z x, pokud je menší než nastavená
a,4
x0
c,x2
c,x2
a,x4
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,c7
e,8
b,12
y
2
4
9
5
8
5
6
108 1 3
9
f
7
2
4
4
start
cíl
a
x0
c,x2
a,x4
odebereme vrchol s nejmenší hodnotou
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,x2
a,x4
d,c7
e,8
b,12
y
2
4
9
5
8
5
6
108 1 3
9
f
7
2
4
4
start
cíl
a
x0
c,x2
a,x4
odebereme vrchol s nejmenší hodnotou
d,c7
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,8
b,12
y, 16
2
4
9
5
8
5
6
108 1 3
9
f,9
7
2
4
4
start
cíl
a
x0
c,2
a,4
upravíme hodnoty ve vrcholech
d,7
x0
a,x4
c,x2
d,c7
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,12
y, 16
2
4
9
5
8
5
6
108 1 3
9
f,9
7
2
4
4
start
cíl
a
x0
c,2
a,4
odebereme vrchol s nejmenší hodnotou
d,7
x0
a,x4
c,x2
d,c7
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,12
y, 16
2
4
9
5
8
5
6
108 1 3
9
f,9
7
2
4
4
start
cíl
a
x0
c,2
a,4
odebereme vrchol s nejmenší hodnotou
d,7
x0
a,x4
c,x2
d,c7
e,x8
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,12
y, 16
2
4
9
5
8
5
6
108 1 3
9
f,9
7
2
4
4
start
cíl
a
x0
přehodnotíme vrcholy
d,c7
x0
a,x4
c,x2
d,c7
e,x8
c,x2
a,x4
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,12
y, 16
2
4
9
5
8
5
6
108 1 3
9
f,d9
7
2
4
4
start
cíl
a
odebereme vrchol s nejmenší hodnotou
x0
a,x4
c,x2
d,c7
x0
d,c7
e,x8
c,x2
a,x4
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,12
y, 16
2
4
9
5
8
5
6
108 1 3
9
f,d9
7
2
4
4
start
cíl
a
odebereme vrchol s nejmenší hodnotou
x0
a,x4
c,x2
d,c7
f,d9
x0
d,c7
e,x8
c,x2
a,x4
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,12
y, 16,13
2
4
9
5
8
5
6
108 1 3
9
f,d9
7
2
4
4
start
cíl
a
přehodnotíme vrcholy
x0
a,x4
c,x2
d,c7
f,d9
x0
d,c7
e,x8
c,x2
a,x4
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,a12
y, 16,13
2
4
9
5
8
5
6
108 1 3
9
f,d9
7
2
4
4
start
cíl
a
odebereme vrchol s nejmenší hodnotou
x0
a,x4
c,x2
d,c7
f,d9
x0
d,c7
e,x8
c,x2
a,x4
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,a12
y, 16,13
2
4
9
5
8
5
6
108 1 3
9
f,d9
7
2
4
4
start
cíl
a
odebereme vrchol s nejmenší hodnotou
x0
a,x4
c,x2
d,c7
e,x8
f,d9
b,a12
x0
d,c7
c,x2
a,x4
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,a12
y, 16,f13
2
4
9
5
8
5
6
108 1 3
9
f,d9
7
2
4
4
start
cíl
a
zůstal poslední vrchol, přehodnocovat jej nebudeme, protože by hodnota nebyla menší.
x0
a,x4
c,x2
d,c7
e,x8
f,d9
b,a12
y, 16,f13
x0
d,c7
c,x2
a,x4
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,a12
y, 16,f13
2
4
9
5
8
5
6
108 1 3
9
f,d9
7
2
4
4
start
cíl
a
Nyní zrekonstruujeme cestu od konce
x0
a,x4
c,x2
d,c7
e,x8
f,d9
b,a12
y, 16,f13
x0
d,c7
c,x2
a,x4
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,a12
y, 17,f13
2
4
9
5
8
5
6
108 1 3
9
f,d9
7
2
4
4
start
cíl
a
Nyní zrekonstruujeme cestu od konce
x0
a,x4
c,x2
d,c7
e,x8
f,d9
b,a12
y, 16,f13
x0
d,c7
c,x2
a,x4
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,a12
y, 16,f13
2
4
9
5
8
5
6
108 1 3
9
f,d9
7
2
4
4
start
cíl
a
x0
c,x2
a,x4
Nyní zrekonstruujeme cestu od konce
d,c7
x0
a,x4
c,x2
d,c7
e,x8
f,d9
b,a12
y, 16,f13
NALEZENÍ NEJKRATŠÍ CESTY V GRAFU
Dijkstrův algoritmus
x0
c,2
a,4
d,7
e,x8
b,a12
y, 16,f13
4
9
5
86
108 1 3
9
f,d9
7
4
start
cíl
a
x0
c,x2
a,x4
Nyní zrekonstruujeme cestu od konce
d,c7
x0
a,x4
c,x2
d,c7
e,x8
f,d9
b,a12
y, 16,f13
2
5
2
42 + 5 + 2 + 4 = 13
