Dextra algoritmus a jeho implementace

V matematice a informatice existuje samostatný směr nazvaný teorie grafů. V rámci tohoto rámce jsou nastaveny a řešeny různé úkoly, například o nalezení nejkratší cesty mezi vrcholy. Jeden z nejběžnějších metod pro řešení tohoto problému mezi matematiky byl již dávno algoritmus Dijkstra.

Co je matematický graf

Předpokládá se, že koncept grafu byl zaveden v osmnáctém století Leonardem Eulerem. Byl to ten, kdo vyjádřil formulaci a řešení jednoho z klasických problémů této teorie - o sedmi mostách Koenigsbergu. Abychom vysvětlili předmět této teorie, nejčastěji používají analogii jako pohyb mezi různými městy. Graf v rovině bude představovat celou schéma tras, kde vrcholy budou specifické body (například města) a hrany - cesta z jednoho vrcholu k druhému (obdoba cesty mezi městy). Dijkstrův algoritmus může vedle jiných metod poskytnout řešení této otázky.

Hledání nejkratší cesty

Jedna ze standardních úkolů teorie grafů je ten, ve kterém je nutné určit nákladově optimální cestu mezi dvěma body. Může být snížena v rovině na řešení grafu, ve kterém jsou vrcholy - města - propojeny hranami, které představují možné cesty. A každá silnice má svou vlastní délku, a proto projet přes ni bude muset vynaložit určité prostředky. Tato suma je ekvivalentní hmotnosti hrany na grafu. Poté může být problém v praxi formulován následovně: jak připravit cestu z jednoho města do druhého, vynaložit minimální prostředky na cestu.

Řešení

Pro řešení tohoto problému byly vynalezeny některé algoritmy, které se ve vědeckém světě staly široce známými. Například algoritmus Floyd - Warshell, Ford - Bellman. Algoritmus Dijkstra je také klasickým způsobem nalezení řešení. Může se také použít pro váhu (gramáž každé hrany je známa) a pro řídké. Chcete-li najít konečnou cestu, musíte udělat několik kroků.

Algoritmus Dijkstra

Význam této metody spočívá v tom, že všechny vrcholy jsou vynechány, začínající od daného, ​​každý z nich má štítek s určitou hodnotou. Výsledek bude zahrnovat ty vrcholy, jejichž štítky jsou minimální. V prvním kroku je původnímu vertexu přiřazen štítek s hodnotou 0. Potom jsou vzaty v úvahu všechny následující vrcholy, to znamená ty, které lze získat z zdrojového vrcholu. Jsou přiřazeny štítky, jejichž hodnota je definována jako součet zdroje a hmotnost cesty. Z vrcholů dalšího kroku se vybírá jeden, který má nejmenší hodnotu štítku, a jsou zkoumány všechny vrcholy, kterým může být překročena bez použití mezilehlých vrcholů. Je definována nová hodnota štítku, která se rovná značce zdrojového vrcholu a hmotnosti cesty. Pokud je výsledná hodnota menší než značka vrcholu, změní se její označení. V opačném případě zůstává původní hodnota. V tomto případě, v samostatném poli, jehož rozměr se rovná počtu vrcholů grafu, je zachován výsledek optimalizace, podél kterého je určena cesta. Pro implementaci takové metody jako Dijkstra algoritmus, Pascal nabízí velmi pohodlné nástroje. Tento algoritmus má tu výhodu, že může být snadno použit jako základ programu, který má malou velikost. Příklady takových softwarových produktů lze snadno najít na internetu.

K vyřešení problému nalezení optimální cesty lze použít různé prostředky. Pro takové řešení, jako je Dijkstraův algoritmus, vytvoří Delphi vizuální vhodnou formu vstupu vstupních dat a výstupu konečného výsledku.