Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV

3. Vybrané problémy / Hledání nejkratší cesty v grafu

Úvod

Hledání nejkratší cesty je jedním ze základních problémů teorie grafů - podobné algoritmy se používají např. v plánovačích tras v GPS nebo v jízdních řádech.

Mějme souvislý graf s metrikou. Tím jsme získali "mapu" (víme, odkud a kam vedou silnice a jak jsou dlouhé) - jediné informace, které algoritmus potřebuje.

Floyd-Warshallův algoritmus

Jedním z algoritmů pro hledání nejkratší cesty je Floyd-Warshallův algoritmus. Jeho výhodou je velmi snadné použití.

Princip algoritmu

Algoritmus postupně projde všechy možnosti cest mezi každými dvěma městy a pokud zjistí, že cesta přes třetí město by byla kratší, použije ji.

Vzdálenost(A,B) = min(Vzdálenost(A,B), Vzdálenost(A,C)+Vzdálenost(C,B)).

Užitečnou vlastností tohoto algoritmu je také, že najde vzdálenost mezi každými dvěma městy (i pokud mezi nimi původně nevedla přímá silnice).

Implementace

Podobně jako u matice sousednosti v počítači použijeme dvourozměrné pole. Mezi městy, která nejsou spojena silnicí, je použita vysoká konstanta představující nekonečno (v konkrétním případě 999, konstanta musí být dostatečně vysoké číslo, často se používá součet délek silnic + 1); mezi městy, která silnicí spojeny nejsou, bude v matici (poli) uložená délka cesty.
Samotný algoritmus je vlastně užití standardní funkce minimum ze dvou čísel spuštěné ve třech for cyklech v sobě.

Řešení ve formě programu - stáhnout celý program (zdrojový kód, Pascal, 3 kB)

GeSHi © 2004, Nigel McNie
  1. procedure nejkratsiCesta(var matice:typ_matice);
  2. var
  3.  i, j, k: integer;
  4. begin
  5.   for i:=1 to velikost_matice do
  6.     begin
  7.     for j:=1 to velikost_matice do
  8.       begin
  9.       for k:=1 to velikost_matice do
  10.         begin
  11.         matice[i,j]:= minimum(matice[i,j], (matice[i,k] + matice[k,j]));
  12.         end; { k }
  13.       end; { j }
  14.     end; { i }
  15. end;

Nevýhody

Velkým problémem tohoto algoritmu je ovšem jeho výpočetní složitost - s tím, jak roste počet vrcholů, mezi kterými vzdálenost počítáme, roste počet kroků algoritmu podobně jako graf funkce y = x3.

Pro více informací hledejte...

Jedním z lépe použitelných algoritmů je Dijkstrův algoritmus. Dosahuje rychlejšího výpočtu, samotná implementace je ovšem náročnější než u Floyd-Warshallova algoritmu.

Výpočetní náročnost algoritmů podle velikosti vstupních dat se v informatice zkoumá pomocí tzv. (časové) složitosti algoritmu (viz [9]).

Úvod

Základní pojmy

Vybrané problémy

Procvičování

Zdroje a literatura