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 nenegatīvām šķautņu ceļu izmaksām, 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ākajma ceļam no vienas virsotnes līdz citai virsotnei, apturot algoritmu, tiklīdz šis īsākais ceļs 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 pērē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).
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. |