Dijkstra’s Shortest Path
December 24th, 2009
2 comments
There was an infamous professor at my university with a multiple choice exam question:
What is the correct spelling of Edsger
(A) Dykstra
(B) Dikstra
(C) Dijkstra
(D) Dyjkstra
I never did forget how to spell it—it’s the fact that I-J-K appears in order that helps you to remember.
Anyway, one of Dijkstra‘s most famous algorithms is one to find the shortest path through a graph. The graph is a set of vertices connected by weighted edges. Or, more concretely, a set of cities connected by roads of varying lengths. The question is, what’s the shortest path from Copenhagen to Stuttgart?
