Autor : David Ježek , L95624

Prohledávání do šířky

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

Nalezení nejkratší cesty pomocí prohledávání grafu do šířky se realizuje v těchto krocích: začneme ve výchozím uzlu u[v] a prozkoumáme všech sousední uzly (všechny uzly pro které můžeme zlepšit cenu pomocí trojůhelníkové nerovnosti, tuto cenu zlepšíme a přídáme je do fronty). Pak se přesuneme do uzlu na začátku fronty a vše opakujeme. Tento algoritmus můžeme ukončit v různých situacích:
kdyľ dojdeme do předem vybraného vrcholu.
když je fronta prázdná(prozkoumali jsme jednu souvislou komponentu).

Algoritmus:

Budeme používat pole cen C, kde si uložíme cenu nejlevnější cesty. Dále použijeme frontu F, kam budeme postupně ukládat procházené uzly (konkrétně jejich indexy).

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

2.Pro všechny sousedy u[k] uzlu u[i] ze začátku fronty, pro který můžeme zlepšit cenu pomocí trojůhelníkové nerovnosti C[k] > C[i]+c[ki], provedeme {C[k]=C[i]+c[ki]}, a vložíme je do fronty.

3. Je-li fronta prázdná přejdeme na bod 4, jinak pokračujeme bodem 2.

4. Koneck

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.