Dijkstra's Algorithm


This article celebrates a classic algorithm [1] of Dijkstra (1930 – 2002) which finds a path of minimal cost between any pair of nodes in an undirected graph. His procedure is widely recognized as a fundamental tool for examining communication and transportation networks (eg. Google Maps) and is surprisingly simple. By his own admission, he solved this problem in twenty minutes while having coffee with his fiancée Ria [2].

The presentation below views his minimal path problem as coloring the nodes of a weighted undirected graph, in a certain order, to converge on a minimal path, and uses mathematical