Deikstras algoritms

Deikstras algoritms
	Deikstras algoritma darbība
Klase	Meklēšanas algoritms
Datu struktūra	Grafs
Sliktākā ātrdarbība

Deikstras algoritms ir grafu meklēšanas algoritms, kurš risina viena izejas stāvokļa īsākā ceļa problēmu grafiem ar negatīiem šķ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.

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|²). 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.

Atsauces

↑ Dijkstra, Edsger; Thomas J. Misa, Editor (2010-08). "An Interview with Edsger W. Dijkstra". Communications of the ACM 53 (8): 41–47. doi:10.1145/1787234.1787249. "What is the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path which I designed in about 20 minutes. One morning I was shopping with my young fianceé, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path."
↑ Dijkstra 1959

Šis ar informācijas tehnoloģijām saistītais raksts ir nepilnīgs. Jūs varat dot savu ieguldījumu Vikipēdijā, papildinot to.

[Dijkstra_Interview-1] Dijkstra, Edsger; Thomas J. Misa, Editor (2010-08). "An Interview with Edsger W. Dijkstra". Communications of the ACM 53 (8): 41–47. doi:10.1145/1787234.1787249. "What is the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path which I designed in about 20 minutes. One morning I was shopping with my young fianceé, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path."

[2] Dijkstra 1959

[1]

[2]