Dijkstra shortest path algorithm
Algoritmo de Dijkstra de caminos mínimos
- Date
- 1956 · confidence high
- Place
- Amsterdam (Mathematisch Centrum), Netherlands
- Credited to
- Edsger W. Dijkstra (conceived in 1956, published in 1959)
- People
- 👤 Edsger Dijkstra1930–2002
- Field
- Knowledge & symbols
What was discovered
An efficient algorithm that finds the lowest-cost path from a source to every node of a graph with non-negative weights. The prototype of a greedy algorithm and a central piece of algorithmics.
Dijkstra devised it in twenty minutes on a café terrace while thinking about the map of the Netherlands.
What it led to
- algorithmics and the analysis of algorithms
- A* and heuristic search
- routing protocols (OSPF)
Built on
- Graph theory: seven bridges of Königsberg1736
- Bellman's dynamic programming
Made possible
- Floyd–Warshall algorithm1959-1962
- A* search algorithm1968
- Car navigation system1981-1990
- Ant colony optimization algorithm1992
- GPS navigators
- internet routing
- robot motion planning