Dijkstrov algoritmus a jeho implementácia

Tam je oddelený priestor s názvom teórie grafov v matematike a informatike. Ako súčasť svojej sady a riešiť rôzne problémy, ako je napríklad hľadanie najkratšiu cestu medzi vrcholmi. Jeden obyčajný medzi matematici spôsobov riešenia tohto problému je už dlho Dijkstrov algoritmus.

To, čo je matematický graf

Predpokladá sa, že pojem grafu bola uvedená do prevádzky v osemnástom storočí Leonardom Eylerom. Bol to on, kto oznámil formuláciu a riešenie jedného z klasických problémov tejto teórie - sedem mostov Königsberg. Aby bolo možné vysvetliť predmetom tejto teórie často používajú túto analógiu ako pohyb medzi jednotlivými mestami. Potom graf v rovine bude celá trasa diagram, kde vrcholy stáť konkrétne položky (napr mestá), a hrany - cesta od jedného vrcholu do iného (analógový ceste medzi mestami). Dijkstrov algoritmus, okrem iných metód, môže poskytnúť riešenie tohto problému.

Nájdenie najkratšej cesty

Jedným zo spoločných úloh teórie grafov je ten, v ktorom je potrebné určiť optimálnu cestu nákladov medzi dvoma bodmi. Je možné znížiť lietadlo rozhodnutie graf, v ktorom vrcholy - Mestá - sú prepojené rebrami, ktorý je možný cesty. Každá cesta má svoju vlastnú dĺžku, a preto cestovať na nej bude musieť minúť nejaké peniaze. Toto množstvo je ekvivalentná hmotnosti hrán v grafe. Potom je problém v praxi možno formulovať takto: Ako vytvoriť cestu z jedného mesta do druhého, ktoré majú byť vynaložené na ceste minimálnymi prostriedkami.

spôsoby, ako riešiť

Na vyriešenie tohto problému sme boli vynašiel niektoré algoritmy, ktoré sa stali široko známymi vo vedeckom svete riešiť. Napríklad Floyd algoritmus - Uorshella, Ford - Bellman. Klasický spôsob, ako nájsť riešenie, je tiež Dijkstrov algoritmus. Môže byť použitý pre vážený (známej hmotnosti každej hrany) v grafe, a riediť. Pri hľadaní najvhodnejšieho spôsobu je nutné vykonať niekoľko krokov.

Dijkstrov algoritmus

Zmyslom tohto spôsobu spočíva v tom, že všetky vrcholy nákladov, počnúc daná, pričom každá značka je priradená určitú hodnotu. Potom výsledok bude obsahovať vrcholy, ktorých štítky sú minimálne. Na hornú časť prvej počiatočnom kroku budú označené s hodnotou 0. Potom sa všetky tieto vrcholy sú považované, teda tých, ktoré môže byť dosiahnuté zo zdroja. Sú označené, ktorého hodnota je určená ako súčet zdrojového kódu a hmotnosti ciest. Z vrcholu k ďalšiemu kroku, vyberte ten, ktorý má najmenšiu hodnotu štítku a študoval všetky vrcholy v tom, že z nej môžeme ísť bez použitia medziľahlých uzlov. Zadajte nový štítok rovnajúcu sa štítky vrcholy - zdrojový kód, plus hmotnosť cesty. Ak je hodnota menšia ako horná štítok, štítok sa zmení. V opačnom prípade zostane pôvodná hodnota. Zároveň sa v samostatnom poli, ktorej rozmer je rovný počtu vrcholov, uloží výsledok optimalizácie, v ktorom a rozhodným spôsobom. Implementovať metódy, ako Dijkstrov algoritmus, Pascal ponúka veľmi pohodlný spôsob. Algoritmus má tú výhodu, že môže byť ľahko základom pre program, ktorý má malú veľkosť. Príklady takýchto softvérových produktov ľahko nájsť na internete.

PODĽA riešenie rôzne nástroje, ktoré možno použiť za úlohu nájsť optimálnu cestu. Pre riešenie, ako Dijkstrov algoritmus, bude Delphi vytvoriť výhodnú formu vizuálnej dátový vstup a výstup konečný výsledok.