Autor : David Ježek , L95624

Prohledávání do hloubky

Nalezení nejkratší cesty pomocí prohledávání grafu do hloubky

Nalezení nejkratší cesty pomocí prohledávání grafu do hloubky se realizuje v těchto krocích: začneme ve výchozím uzlu u[v] a přejdeme do kterehokoliv sousedního uzlu splňujícího běžnou trojůhelníkovou nerovnost. U tohoto uzlu změníme cenu a testujeme, jestli můžeme pokračovat v procházení grafu tak abychom zlepšily minimální ceny. Pokud ano, přesunem se do dalšího uzlu, u kterého si také změníme cenu. Pokud nejsou v okolí vrcholu dosud uzly u kterých bychom mohli zlepšit cenu, vracíme se zpět a testujeme okolí dřívějších uzlů. Tento algoritmus můžeme ukončit v různých situacích:
kdyľ dojdeme do předem vybraného vrcholu.
když se vrátíme zpět do výchozího uzlu (prozkoumali jsme jednu souvislou komponentu).

Algoritmus:

Budeme používat pole cen C, kde si uložíme cenu nejlevnější cesty. Dále použijeme zásobník Z, kam budeme postupně ukládat procházené uzly (konkrétně jejich indexy) a zpět se po nich vracet.

1. Inicializace - C[v] := 0; C[i] := MAXFLOAT pro všechna i mimo i <>V, kde v je index výchozího uzlu. Na zásobník vložíme index výchozího vrcholu.

2. Hledáme sousední uzlu u[k] k uzlu na vrcholu zásobníku, pro který můžeme zlepšit cenu pomocí trojůhelníkové nerovnosti C[k] > C[i]+c[ki], pak {C[k]=C[i]+c[ki]}, a vložíme k na zásobník.
Pokud neexistuje hrana splňující tuto podmínku Odebereme vrchol zásobníku.

3. Je-li zásobník prázdný přejdeme na bod 4, jinak pokračujeme bodem 2.

4. Konec

Může se použít také pole Pu pokud chceme znát přesný sled hran které tvoří nejkratší cestu. Hodnota MAXFLOT je brána jako nekonečno a předpokládá se, že při výpočtu (sčítání, násobení) tato hodnota nebude dosažena. Dále je zde použito pole delka[99] ktere reprezentuje počet hran nejlevnější cesty pro daný uzel, pokud pro nějaký uzel překročí toto číslo celkový počet hran grafu, pak v grafu existuje kružnice se zápornou cenou a algoritmus končí.
Pole cen je vyplněno hodnotami MAXFLOAT pouze pro počáteční uzel je hodnota 0 . Dále algoritmus pokračuje podle výše uvedeného postupu.

Algoritmus označí všechny uzly dosažitelné z počátečního a vypíše minimálni cenu za kterou je možno se do uzlu dostat.