The Shortest-Paths Problem

“All roads lead to Rome,” says an old proverb.

But faced with sundry choices about which road to take to get to a destination, how does one decide? An obvious choice is the shortest one. Common sense may caution against routes with traffic congestion or routes that are expensive in terms of time or money.

With such factors in place, when we start thinking about algorithmically finding the best possible route to our destination, we need a clean-cut model that is flexible enough to adapt to our preferences for what qualifies as best.

A network as a weighted digraph

The network of roads in such a case is typically represented as a weighted digraph. Each site in the network is represented as a vertex, and each road is modeled as an edge with a number associated with it called the weight of that edge.

The weight may represent the distance between the ends of the edge, or it may represent some other cost, such as the time taken to traverse the road or a monetary cost associated with traveling that road. In fact, depending on the application, the edge weights are even allowed to be negative. Finally, the network under scrutiny may be other than a road network.

We represent the edge weights of a simple weighted digraph using a two-dimensional $n \times n$ array, where $n$ is the number of vertices. For each edge ...