Programming Praxis

[ 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 OSPF (Open Shortest Path First).

For instance, in the digraph pictured at right, the shortest path from vertex a to e is [a, c, e]. This path has a length of 7, which is shorter than the path [a, d, e] (which has a length of 16).

The algorithm works its way through the vertices, indexed by their estimated distance from the starting point. At each vertex, the procedure “relaxes” all its outward edges, updating distance and predecessor estimates accordingly. Once complete, the algorithm has in effect constructed a subtree of the graph that gives all the shortest distance paths from the starting vertex to any other vertex in the graph via the predecessor attribute. The shortest path to the desired finishing vertex can then be reconstructed by traversing the predecessor subtree backwards. See Dijkstra’s 1959 paper “A Note on Two Problems in Connexion with Graphs” in Numerische Mathematik (Volume 1, pages 269-271) for more information.

Your task: given a weighted digraph D = (V, E) where the edge weights represent distances between two vertices, a starting vertex s, and a destination vertex f, use Dijkstra’s Algorithm to find the shortest path from s to f in G. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2