Dextra algoritms un tā ieviešana
Matemātikas zinātnē un datorzinātnē irAtsevišķs virziens, ko sauc par grafu teoriju. Tās ietvaros tiek noteikti un atrisināti dažādi uzdevumi, piemēram, par īsāko ceļu atrašanu starp virsotnēm. Viena no visbiežāk sastopamajām metodēm šīs problēmas risināšanai matemātikā jau sen ir Dijkstra algoritms.
Tiek uzskatīts, ka grafikā tika ieviests jēdziensLeonarda Eulera izmantošana astoņpadsmitajā gadsimtā. Tas bija tas, kurš pauda formulējumu un risinājumu kādai no šīs teorijas klasiskajām problēmām - par septiņiem Koenigsberga tiltiem. Lai izskaidrotu šīs teorijas priekšmetu, visbiežāk tiek izmantota tāda analoģija kā kustība starp dažādām pilsētām. Tad plaknē esošais grafiks būs visa maršruta shēma, kurā virsotnēs būs konkrēti punkti (piemēram, pilsētas), un malas - ceļi no vienas pīķa uz otru (līdzīgi ceļiem starp pilsētām). Dijkstra algoritms, papildus citām metodēm, var sniegt risinājumu šim jautājumam.
Viena no grafikas teorijas standarta problēmām irkurā ir nepieciešams noteikt izmaksu ziņā optimālu ceļu starp diviem punktiem. To var samazināt plaknē uz grafika risinājumu, kurā virsotnes-pilsētas savstarpēji savienotas ar malām, kas attēlo iespējamos ceļus. Un katram ceļam ir savs garums, tādēļ ceļā caur to būs jāpiešķir noteikti līdzekļi. Šī summa ir ekvivalenta grafa svara vērtībai. Tad praksē problēmu var formulēt šādi: kā nobloķēt ceļu no vienas pilsētas uz otru, tērēt uz ceļa minimālos līdzekļus.
Risinājumi
Lai atrisinātu šo problēmu, dažialgoritmi, kas ir kļuvuši plaši pazīstami zinātnes pasaulē. Piemēram, algoritms Floyd - Warshell, Ford - Bellman. Dijkstra algoritms ir arī klasisks veids, kā atrast risinājumu. To var arī izmantot svērto (katras malas svars ir zināms) grafiks, un reti. Lai atrastu pēdējo ceļu, jums ir jāveic dažas darbības.
Dijkstra algoritms
Šīs metodes nozīme ir tāvisi virsotnes ir apietas, sākot ar konkrētu, katram tiek piešķirta etiķete ar noteiktu vērtību. Tad rezultāts ietvers tās virsotnes, kuru etiķetes ir minimālas. Pirmajā solī sākotnējam virsotnēm piešķir etiķeti ar vērtību 0. Tad tiek ņemtas vērā visas tālāk minētās virsmas, tas ir, tās, kurām var piekļūt no avota virsotnes. Tiem tiek piešķirtas etiķetes, kuru vērtību nosaka kā avota summu un ceļa svaru. No nākamā posma virsotnes tiek izvēlēts viens, kas ir mazākais etiķetes vērtība, un tiek pētītas visas virsotnes, kurās to var pārvietot, neizmantojot starpposmu virsotnes. Ir noteikta jauna etiķetes vērtība, kas ir vienāda ar avota virsotnes marķējumu un ceļa svaru. Ja iegūtā vērtība ir mazāka nekā virsotnes etiķete, tad etiķete mainās. Pretējā gadījumā sākotnējā vērtība paliek. Šajā gadījumā atsevišķā masīvā, kura izmērs ir vienāds ar diagrammas virsotņu skaitu, tiek saglabāts optimizācijas rezultāts, pa kuru nosaka ceļu. Lai īstenotu šādu metodi kā Dijkstra algoritmu, Pascal piedāvā ļoti ērtus rīkus. Algoritmam ir priekšrocība, ka to var viegli izmantot kā neliela izmēra programmas pamatu. Šādu programmatūras produktu piemērus ir viegli atrast internetā.
