Matemātikā un datorzinātnēs iratsevišķs virziens, ko sauc par grafu teoriju. Tās ietvaros ir radušās un atrisinātas dažādas problēmas, piemēram, atrast īsāko ceļu starp virsotnēm. Viens no visbiežāk izmantotajiem veidiem, kā matemātiķi atrisināt šo problēmu, jau sen ir bijis Dijkstra algoritms.
Tiek uzskatīts, ka grafika jēdziens tika ieviests 2006. \ T18. gadsimtā Leonard Euler. Tas bija viņš, kurš izteica viena no šīs teorijas klasiskajām problēmām - septiņiem Koenigsbergas tiltiem. Lai izskaidrotu šīs teorijas mērķi, visbiežāk izmanto šo analoģiju, kā kustību starp dažādām pilsētām. Tad plaknē esošā diagramma attēlo visu maršruta karti, kur virsotnes būs konkrēti punkti (piemēram, pilsētas), un malas būs ceļi no viena virsotnes uz citu (līdzīgi ceļam starp pilsētām). Dijkstra algoritms, papildus citām metodēm, var sniegt risinājumu šim jautājumam.
Viena no grafu teorijas standarta problēmām irviens, kurā jums jānosaka rentabls ceļš starp diviem punktiem. To plaknē var reducēt līdz grafika risinājumam, kurā virsotnes - pilsētas - savieno malas, kas apzīmē iespējamos ceļus. Turklāt katram ceļam ir savs garums, tāpēc, braucot pa to, būs jāizlieto noteikti līdzekļi. Šī summa ir vienāda ar malas svaru grafikā. Tad problēmu praksē var formulēt šādi: kā bruģēt ceļu no vienas pilsētas uz otru, lai ceļā iztērētu minimālus līdzekļus.
Risinājumi
Lai atrisinātu šo problēmu, dažialgoritmi, kas kļuvuši plaši pazīstami zinātnes pasaulē. Piemēram, Floyd-Warshall, Ford-Bellman algoritms. Dijkstra algoritms ir arī klasisks veids, kā atrast risinājumu. To var izmantot gan svērtajam (mēs zinām katras malas svaru), gan retam grafikam. Lai atrastu galīgo ceļu, jums jāiziet vairākas darbības.
Dijkstra algoritms
Šīs metodes jēga ir tādavisas virsotnes tiek šķērsotas, sākot ar doto, un katrai no tām tiek piešķirta iezīme ar kādu vērtību. Tad rezultāts ietvers tās virsotnes, kuru etiķetes ir minimālas. Pirmajā posmā sākotnējai virsotnei tiek piešķirta etiķete ar vērtību 0. Pēc tam tiek ņemtas vērā visas šīs virsotnes, tas ir, tās, kuras var sasniegt no oriģināla. Viņiem tiek piešķirtas etiķetes, kuru vērtību nosaka kā avota un ceļa svara summu. No nākamā soļa virsotnēm tiek izvēlēta tā, kurai ir mazākā etiķetes vērtība, un tiek pētītas visas virsotnes, kuras no tās var sasniegt, neizmantojot starpposma virsotnes. Tiek noteikta jauna etiķetes vērtība, kas vienāda ar avota virsotnes etiķeti plus ceļa svaru. Ja saņemtā vērtība ir mazāka par virsotnes etiķeti, tad iezīme tiek mainīta. Pretējā gadījumā sākotnējā vērtība paliek. Šajā gadījumā atsevišķā masīvā, kura dimensija ir vienāda ar virsotņu skaitu diagrammā, tiek saglabāts optimizācijas rezultāts, pēc kura tiek noteikts ceļš. Lai ieviestu tādu metodi kā Dijkstra algoritms, Paskāls piedāvā ļoti ērtus rīkus. Algoritmam ir tā priekšrocība, ka to var viegli izmantot par pamatu maza izmēra programmai. Šādu programmatūras produktu piemērus ir viegli atrast internetā.
