Deikstras algoritms
From Wikipedia, the free encyclopedia
Deikstras algoritms ir grafu meklēšanas algoritms, kurš risina viena izejas stāvokļa īsākā ceļa problēmu grafiem ar nenegatīviem šķautņu svariem, izveidojot īsākā ceļa koku. To 1956. gadā radīja un 1959. gadā publicēja[1][2] nīderlandiešu datorzinātnieks Edsgers Deikstra. Šo algoritmu bieži izmanto maršrutēšanā un kā apakšprocedūru citiem grafu algoritmiem.
Deikstras algoritma darbība | |
Klase | Meklēšanas algoritms |
---|---|
Datu struktūra | Grafs |
Sliktākā ātrdarbība |
Algoritms dotajai grafa virsotnei (mezglam) atrod ceļu ar viszemākajām izmaksām (t.i. īsāko ceļu) starp šo un katru citu virsotni. To var izmantot arī, lai atrastu izmaksas īsākajam ceļam no vienas virsotnes līdz citai virsotnei, apturot algoritmu, tiklīdz šis īsākais ceļš ir noteikts. Piemēram, ja grafa virsotnes attēlo pilsētas un šķautņu ceļa izmaksas attēlo nobraucamo attālumu starp pilsētām pa savienojošu ceļu, Deikstras algoritmu var izmantot, lai atrastu īsāko ceļu starp vienu pilsētu un visām citām parējām. Tā rezultātā īsākā ceļa atrašanu plaši izmanto tīkla maršrutēšanas protokolos, zināmākie no tiem IS-IS un OSPF (Open Shortest Path First).
Deikstras sākotnējais algoritms neizmanto minimālo prioritāšu rindu un darbojas ar novērtējumu O(|V|2). Biežākā realizācija izmanto minimālo prioritāšu rindu, ko realizē ar Fibonači kaudzi un tā darbojas ar novērtējumu O(|E| + |V| log |V|). Tas ir asimptotiski ātrākais zināmais vienas izejas īsākā ceļa meklēšanas algoritms patvaļīgiem grafiem ar nenegatīviem šķautņu svariem.