Concept
Dijkstra's Algorithm
DYKE-struhz algorithm
Also Known As Dijkstra's Shortest Path Algorithm
Algorithm
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 FAQs
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.
Connections
In Field
Invented By
Source Wikipedia: Dijkstra's Algorithm
Sources
1. Wikipedia: Dijkstra's Algorithm
Wikimedia FoundationLead section
Dijkstra's algorithm (, DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network.
History section
It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
In Group: Graph Algorithms, Lead
Dijkstra's algorithm (, DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network.
View the Source 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.