January 4, 2011 [ Today's exercise was written by guest author
Graham Enos, a PhD student in the Applied Mathematics program at
UNC Charlotte, with solution in Python rather than Scheme.
Suggestions for exercises are always welcome, or you may wish to
contribute your own exercise; feel free to contact me if you are
interested. ] We’ve worked with directed graphs (“digraphs”) in
a recent exercise. Today’s exercise is another graph theoretical
procedure with many applications: Dijkstra’s Algorithm.
Published by Edgar Dijkstra in 1959, this algorithm searches a
digraph for the shortest paths beginning at a specified vertex;
to quote the Wikipedia article, For example, if the vertices of
the graph represent cities and edge path costs represent driving
distances between pairs of cities connected by a direct road,
Dijkstra’s algorithm can be used to find the shortest route
between one city and all other cities. As a result, the shortest
path first is widely used in network routing protocols, most
notably IS-IS and