Dijkstras algoritme
Dijkstras algoritme
| Opkaldt efter | Edsger Dijkstra | |
|---|---|---|
| Baseret på | breadth-first search | |
| Opdager eller opfinder | Edsger Dijkstra | |
| Opdagelse | 1959 | |
| Løser | shortest path problem, pathfinding, single-source shortest path problem | |
| Værste tilfælde tidskompleksitet | , | |
Dijkstras algoritme er en algoritme til at finde den korteste vej på en graf. Metoden blev opfundet af Edsger W. Dijkstra i 1956 og udgivet tre år efter.[1][2]
Referencer
- ^ Frana, Phil (august 2010). "An Interview with Edsger W. Dijkstra". Communications of the ACM. 53 (8): 41-47. doi:10.1145/1787234.1787249.
- ^ Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269-271. doi:10.1007/BF01386390. Arkiveret (PDF) fra originalen 23. januar 2020. Hentet 26. februar 2019.
 | Spire Denne artikel om datalogi eller et datalogi-relateret emne er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den. |
Medier brugt på denne side
Arbcom ru editing.svg
Icon of simple gray pencil. An icon for Russian Wikipedia RFAR page.
Icon of simple gray pencil. An icon for Russian Wikipedia RFAR page.
Dijkstra Animation.gif
Animation, describing Dijkstra's algorithm runtime.
Animation, describing Dijkstra's algorithm runtime.