Dijkstra's algorithm: Difference between revisions

Revision as of 11:37, 6 February 2025

Revision as of 22:22, 6 February 2025

Line 14:

== History ==

{{quote boxblockquote|What is the shortest way to travel from [[Rotterdam]] to [[Groningen]], in general: from given city to given city. [[Shortest path problem|It is the algorithm for the shortest path]], which I designed in about twenty minutes. One morning I was shopping in [[Amsterdam]] with my young fiancée, 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. As I said, it was a twenty-minute invention. In fact, it was published in '59, three years later. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became to my great amazement, one of the cornerstones of my fame.|source=—EdsgerEdsger Dijkstra, in an interview with Philip L. Frana, Communications of the ACM, 2001<ref name="Dijkstra Interview2"/>}}

Dijkstra thought about the shortest path problem while working as a programmer at the [[Centrum Wiskunde & Informatica|Mathematical Center in Amsterdam]] in 1956. He wanted to demonstrate the capabilities of the new ARMAC computer.<ref>{{cite web |date=2007 |title=ARMAC |url=http://www-set.win.tue.nl/UnsungHeroes/machines/armac.html |url-status=dead |archive-url=https://web.archive.org/web/20131113021126/http://www-set.win.tue.nl/UnsungHeroes/machines/armac.html |archive-date=13 November 2013 |website=Unsung Heroes in Dutch Computing History}}</ref> His objective was to choose a problem and a computer solution that non-computing people could understand. He designed the shortest path algorithm and later implemented it for ARMAC for a slightly simplified transportation map of 64 cities in the Netherlands (he limited it to 64, so that 6 bits would be sufficient to encode the city number).<ref name="Dijkstra Interview2" /> A year later, he came across another problem advanced by hardware engineers working on the institute's next computer: minimize the amount of wire needed to connect the pins on the machine's back panel. As a solution, he re-discovered [[Prim's algorithm|Prim's minimal spanning tree algorithm]] (known earlier to [[Vojtěch Jarník|Jarník]], and also rediscovered by [[Robert C. Prim|Prim]]).<ref name="EWD841a2">{{citation |last1=Dijkstra |first1=Edsger W. |title=Reflections on "A note on two problems in connexion with graphs |url=https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD841a.PDF}}</ref><ref>{{citation |last=Tarjan |first=Robert Endre |title=Data Structures and Network Algorithms |volume=44 |page=75 |year=1983 |series=CBMS_NSF Regional Conference Series in Applied Mathematics |publisher=Society for Industrial and Applied Mathematics |quote=The third classical minimum spanning tree algorithm was discovered by Jarník and rediscovered by Prim and Dikstra; it is commonly known as Prim's algorithm. |author-link=Robert Endre Tarjan}}</ref> Dijkstra published the algorithm in 1959, two years after Prim and 29 years after Jarník.<ref>{{cite journal |last1=Prim |first1=R.C. |date=1957 |title=Shortest connection networks and some generalizations |url=http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Prim1957.pdf |url-status=dead |journal=Bell System Technical Journal |volume=36 |issue=6 |pages=1389–1401 |bibcode=1957BSTJ...36.1389P |doi=10.1002/j.1538-7305.1957.tb01515.x |archive-url=https://web.archive.org/web/20170718230207/http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Prim1957.pdf |archive-date=18 July 2017 |access-date=18 July 2017}}</ref><ref>V. Jarník: ''O jistém problému minimálním'' [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp.&nbsp;57–63. (in Czech)</ref>