Floydův algoritmus
Floydův algoritmus slouží především k vyhledání vzdáleností (vzdálenost = délka minimální cesty) v ohodnocených grafech. Algoritmus je založen na porovnání hodnot přímých a nepřímých vzdáleností. Využíváme toho, že hrana 
patří do minimální cesty tehdy, pokud nevede minimální cesta jinudy. Zapsáno matematicky:
Floydův algoritmus je tvořen z následujícími kroky:
- Sestavení matice přímých vzdáleností
přičemž pro prvky 
této matice platí:
pokud 
pokud 
a hrana spojující uzly 
existuje,
pokud a hrana spojující uzly neexistuje.
- Zavedeme pomocnou proměnnou
a položíme 
Tato proměnná představuje index vrcholu, pře který provádíme přepočet.
- Provedeme přepočet jednotlivých prvků matice
podle pravidla 
přičemž nepropočítáváme prvky matice, pro které platí 
(hlavní diagonála matice), prvky, pro které platí 
(leží v řádku či sloupci s indexem ), a prvky 
a 
pro které 
a 
- Pokud
(
je počet vrcholů grafu), potom položíme 
a vracíme se zpět ke kroku 3). Je – li 
je výpočet ukončen a poslední získaná matice je hledanou maticí vzdáleností.
Příklad: V zadaném grafu nalezněte vzdálenosti mezi jednotlivými vrcholy pomocí Floydova algoritmu.
Řešení:
|
|
A
|
B
|
C
|
D
|
|
A
|
0
|
|
|
|
|
B
|
3
|
0
|
|
7
|
|
C
|
3
|
2
|
0
|
|
|
D
|
|
|
4
|
0
|
|
|
K=1
|
A
|
B
|
C
|
D
|
|
A
|
0
|
|
|
|
|
B
|
3
|
0
|
|
7
|
|
C
|
3
|
2
|
0
|
|
|
D
|
|
|
4
|
0
|
|
| |
|
K=2
|
A
|
B
|
C
|
D
|
|
A
|
0
|
|
|
|
|
B
|
3
|
0
|
|
7
|
|
C
|
3
|
2
|
0
|
9
|
|
D
|
|
|
4
|
0
|
|
| |
|
K=3
|
A
|
B
|
C
|
D
|
|
A
|
0
|
|
|
|
|
B
|
3
|
0
|
|
7
|
|
C
|
3
|
2
|
0
|
9
|
|
D
|
7
|
6
|
4
|
0
|
|
