Algoritam dekstra i njegova implementacija

U matematičkoj znanosti i informatici postoji zaseban smjer, nazvan teorijom grafikona. U svom okviru postavljaju se i rješavaju razni zadaci, na primjer, pronalaženja najkraćeg puta između vrhova. Jedna od najčešćih metoda za rješavanje ovog problema među matematičarima dugo je bila algoritam Dijkstra.

Što je matematički graf

Vjeruje se da je koncept grafikona u osamnaestom stoljeću uveo Leonard Euler. Bio je on koji je izrazio formulaciju i rješenje jednog od klasičnih problema ove teorije - o sedam mostova Koenigsberga. Da bi se objasnio objekt ove teorije, najčešće koristi takvu analogiju kao kretanje između različitih gradova. Zatim će grafikon na ravnini predstavljati cijelu shemu ruta, gdje će vrhovi biti određene točke (na primjer, gradovi), a rubovi - put od vrha do vrha (analogno cesti između gradova). Dijkstraov algoritam, uz druge metode, može dati rješenje za ovo pitanje.

Pronalaženje najkraćeg puta

Jedan od standardnih zadataka teorija grafova je onaj u kojem je potrebno utvrditi put optimalnog puta između dvije točke. Može se smanjiti na ravnini do rješenja grafikona u kojoj su gradovi-gradovi-međusobno povezani rubovima, koji predstavljaju moguće ceste. I svaka cesta ima svoju dužinu, stoga će putovati kroz njega morati potrošiti određena sredstva. Ova je suma jednaka težini ruba na grafikonu. Tada se problem u praksi može formulirati na sljedeći način: kako se utrti put iz jednog grada u drugi, da se na putu troši najmanje sredstava.

načina rješavanja

Da bi riješili ovaj problem, izumljeni su neki algoritmi, koji su postali poznati u znanstvenom svijetu. Na primjer, algoritam Floyd - Warshell, Ford - Bellman. Algoritam Dijkstra također je klasičan način pronalaženja rješenja. Također se može koristiti za ponderirani (težina svakog ruba je poznata) graf, a za rijetke. Da biste pronašli konačni put, trebate učiniti nekoliko koraka.

Dijkstra algoritam

Značenje ove metode je da se svi vrhovi zaobilaze, počevši od zadanog, svaki od njih dobiva oznaku s određenom vrijednošću. Tada će rezultat uključivati ​​one čije su oznake minimalne. Na vrhu prve početni korak bit će označena s vrijednošću od 0. tada, sve od sljedećih vrhova smatraju, odnosno one koje se može doći iz izvora. Dodjeljuju se oznake čija je vrijednost definirana kao zbroj izvora i težine staze. S vrha sljedeći korak, odaberite onaj koji ima najmanju vrijednost etiketi, a studirao je sve vrhove, da od nje možemo otići bez korištenja posrednih čvorova. Definirana je nova vrijednost oznake koja je jednaka oznaku izvornog vrška plus težinu staze. Ako je dobivena vrijednost manja od oznake vrhova, oznaka se mijenja. Inače, izvorna vrijednost ostaje. U ovom slučaju, u zasebnom nizu, čija je dimenzija jednaka broju vrhova grafikona, očit je rezultat optimizacije, na kojem se određuje put. Da bi se takva metoda implementirala kao algoritam Dijkstra, Pascal nudi vrlo prikladne alate. Algoritam ima prednost da se lako može koristiti kao osnova za program koji ima malu veličinu. Primjeri takvih softverskih proizvoda lako se mogu pronaći na Internetu.

Kako bi se riješio problem pronalaženja optimalnog puta, mogu se koristiti različiti načini. Za takvo rješenje kao i Dijkstraov algoritam, Delphi će stvoriti vizualni prikladan oblik unosa početnih podataka i izlaza konačnog rezultata.