The shortest path problem and variations of the problem

In this section, we shift our focus to a different graph-related problem: finding the shortest paths between vertices in a network. As we will discuss, this is a problem that is important for routing problems, such as finding the shortest route to travel in a car to a destination or finding the fastest way to deliver a message over a computer network. Shortest path problems have even been used to determine how to use the thrusters on small fleets of deep-space research satellites to move them into very precise positions in relation to one another with minimal fuel usage so that they could work in unison to capture images of stars.

For graphs with unweighted edges, we have previously solved this problem. Let's review this simpler problem and its solution briefly before continuing to the more general problem on networks (that is, weighted graphs). In Chapter 8, Storage and Feature Extraction of Graphs, Trees, and Networks...