BHWS_skripta
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
vzdálenost od sebe bude nulová (1a). Tento uzel se automaticky stane součástí cesty, což
signalizuje hvězdička v kroku 1b. Ve druhém kroku jsou do tabulky vepsány metriky linek
vybraného uzlu, tj. uzlu C. V rámci operace 2b bude vybrán uzel B, protože do něho vede
linka s menší metrikou (11). Uzel B se stane součástí cesty, což je znovu označeno
hvězdičkou. Dále budou vepsány do tabulky metriky linek vedoucích k sousedům naposledy
vybraného uzlu, tj. uzlu B. Protože se cesta počítá od referenčního uzlu C, do tabulky jsou
zapsány celkové metriky od uzlu C. V kroku 3b se znovu vybere nejkratší vzdálenost, která
ještě není součástí cesty, tj. cesta do uzlu D s metrikou 13. Proces vyhodnocení se opakuje tak
dlouho, dokud není nalezena cesta s nejmenším ohodnocením do všech cílových uzlů.
Výsledná cesta je vidět na Obr. 2.10.
Obr. 2.9 Topologie pro Dijkstrův algoritmus
Tab. 2.1 Výsledky iteračních kroků
Směrovače
Iterační kroky
1a
1b
2a
2b
3a
3b
4a
4b
5a
5b
6a
6b
A
∞
∞
∞
∞
35
35
35
35
35
35
35
35*
B
∞
∞
11
11*
11*
11*
11*
11*
11*
11*
11*
11*
C
0
0*
0*
0*
0*
0*
0*
0*
0*
0*
0*
0*
D
∞
∞
13
13
13
13*
13*
13*
13*
13*
13*
13*
E
∞
∞
∞
∞
∞
∞
25
25*
25*
25*
25*
25*
F
∞
∞
∞
∞
∞
∞
33
33
30
30*
30*
30*
16
FEKT Vysokého učení technického v Brně