Dijkstra's algorithm finds the shortest paths between nodes in a weighted graph, which is the abstract form of questions like the fastest road between two cities or the cheapest route through a network. Edsger W. Dijkstra conceived it in 1956, while working as a programmer at the Mathematical Center in Amsterdam, and published it in 1959; it remains a first week staple of every algorithms course and a working part of routing systems everywhere. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Origin YearConceived in 1956; published three years later, in 1959. Core PrincipleGrow the set of nodes whose shortest distance is settled, always extending it through the nearest unsettled node, until the destination is reached. 1 Connections
In Field
Invented By
Source Wikipedia: Dijkstra's Algorithm
Sources
1. Wikipedia: Dijkstra's Algorithm
Wikimedia FoundationOpening and History sections
Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph
History section
It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
View the Source Frequently Asked Questions
How did Dijkstra actually come up with this algorithm?
He worked it out one morning on a cafe terrace in Amsterdam, by his own account, while out shopping with his fiancee.
The algorithm did not come out of a research project. Edsger Dijkstra later described designing it one morning in Amsterdam: he was out shopping with his young fiancee, sat down tired on a cafe terrace for a cup of coffee, and while there worked out the algorithm for the shortest path between two given cities.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.