Slovník | Vyhledávání | Mapa webu
 
Základy informatiky pro biologyTeoretické základy informatiky Teorie grafů Optimalizační úlohy nad grafy Floydův algoritmus

Logo Matematická biologie

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:

  1. Sestavení matice přímých vzdáleností přičemž pro prvky  této matice platí:
    1.  pokud
    2.  pokud  a hrana spojující uzly  existuje,
    3.  pokud  a hrana spojující uzly  neexistuje.
  2. Zavedeme pomocnou proměnnou a položíme Tato proměnná představuje index vrcholu, pře který provádíme přepočet.
  3. 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
  4. 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

 
vytvořil Institut biostatistiky a analýz Masarykovy univerzity | | zpětné odkazy | validní XHTML 1.0 Strict