[ Prostředí ] [ Jarníkův alg. ] [ Borůvkův alg. ] [ Topologické uspořádání ] [ Hledání komponent ] [ Nejkratší cesty ]
Algoritmus pro vyhledávání nejkratších cest ze zadaného vrcholu
pomocí topologického uspořádání vrcholů ( pouze pro acyklické grafy )

Jakub Konštacký, L97726

Princip algoritmu

Algoritmus na vyhledávání nejkratších cest ze zadaného vrcholu využívá topologického uspořádání vrcholů v grafu. Tímto algoritmem lze snížit počet testovaných hran (pokud není výchozí vrchol první v topologickém uspořádání).

Nejprve je třeba vytvořit pomocné pole ( Vstupní stupeň, Předchozí vrchol, Cena hrany )=>(Vs,Pv,C). Pak do tohoto pole vypočteme hodnoty se vstupních údajů do algoritmu ( struktura grafu , výchozí vrchol ). Následuje krok, při kterém zapíšeme do fronty všechny se vstupním stupněm rovným 0. V pomocném poli si tyto vrcholy označíme.

Dále provádíme algoritmus tak dlouho, dokud není fronta prázdná. V této iteraci vybereme z fronty první prvek => zkoumaný vrchol a pro jeho výstupní hrany provedeme toto: 1. Snížíme vstupní stupeň koncového vrcholu hrany, 2.jeli délka (cena) cesty do tohoto vrcholu větší než délka ze zkoumaného vrcholu + délka cesty právě zkoumané hrany, pak nastavíme C na kratší cestu a Pv na zkoumaný vrchol. Tyto kroky ale provádíme pouze od chvíle, kdy jsme vybrali výchozí vrchol z fronty. Opět projdeme vstupní stupně, zařadíme vrcholy do fronty a pokračujeme v iteraci.

Po ukončení iterace zkontrolujeme vstupní stupně, měli by být rovny 0, pokud nemá správné výsledky. Dále se vytvoří graf, který obsahuje všechny původní vrcholy, ale pouze hrany nejkratších cest. ukazatel na tento graf se vrátí jako výsledek do hlavního programu.

 

Implementace algoritmu

Vlastní implementace je v jedné funkci, která jako vstupní parametry dostává celou strukturu grafu a výchozí vrchol nejkratších cest. Výsledkem je ukazatel na novou strukturu grafu nebo v případě chyby ukazatel NULL.

Jako první krok je vytvoření pomocného pole p(Vs,Pv,C) , jako dynamického pole o rozměrech [počet vrcholů]. Dále je toto pole inicializováno na počáteční hodnoty p[i]=(0,0,NEKONEČNO), pak vypočteme a nastavíme pro všechny vrcholy vstupní stupeň a dále nastavíme p[výchozí vrchol]=(Vs,-1,0).

Zde se uloží do fronty všechny vrcholy se Vs=0. Dále se provádí iterace dokud není fronta prázdná. V této iteraci se provedou už výše uvedené změny a opět se přidávají vrcholy se Vs=0 do fronty.
Po ukončení iterace zkontrolujeme vstupní stupně, měli by být rovny 0, pokud ne pak vrací funkce ukazatel NULL ( graf obsahuje cyklus nebo se vyskytla jiná chyba ). Jinak se vytvoří graf, který obsahuje všechny původní vrcholy, ale pouze hrany nejkratších cest. Ukazatel na tento graf se vrátí jako výsledek do hlavního programu.

Ve funkci se využívá fronta, jejíž funkce jsou definovány v hlavičkovém souboru alg5.h

     Funkce se tedy volá:

                                                ukGraf = jméno_funkce (ukGraf,Výchozí vrchol);

    , kde ukGraf je ukazatel na strukturu grafu (TGraf) a Výchozí vrchol je typu int. Funkce nekontroluje správnost vstupních hodnot. 

 

Implementace algoritmu: alg5.cpp

Implementace pomocných funkcí: alg5.h