Diskrētās struktūras datorzinātnēs

Dejkstra algoritms – ir īsākā ceļa atrašana no vienas virsotnes citā. To izgudroja Dejkstrs. Visiem svariem lokos jābūt pozitīviem. Dejkstra algoritms balstās uz maināmu iezīmju piešķiršanas tehniku. Katrā iteracijā grafa virsotnēm tiek pieškirta iezīme. Un šīs iezīmes norāda īsākā ceļa garumu. Sākumvirsotnei tiek piešķirta vērtība 0, bet pārējām virsotnēm pieškir vērtību bezgalība. Algoritma darbības laikā notiek iezīmju maiņa. Katra iterācijā tikai viena iezīme kļūst par konstanti. Šī iezīme norāda īsāko ceļu no sākumvirsotnes uz doto virsotni. Par konstanti kļūst tā iezīme, kura ir mazākā konkrētajā iterācijā.[1]
Algoritma soļi:
Piemēram ir grafs ar patvaļīgo virsotņu skaitu N. Jāsāk meklēt minimālos ceļus no S virsotnes. Masīvā D tiks attēlots rezultāts, uz kuru tiks novietoti visi minimālie garumi no S virsotnes.
No sākuma D masīvu aizpildīsim ar „bezgalības - ” zīmēm, bet virsotnē no kuras jāsāk meklēšanu – S, ievietosim D[S] = 0. Algoritms sastāv no N iterācijām, katra iterācija centīsies uzlabot D masīva rezultātu.…