Chapter Twenty-One Shortest Paths
PATH IN a weighted digraph has an associated path weight, the value of which is sum of the weights of that path’s edges. This essential measure allows us to formulate such problems as “find the lowest-weight
path between two given vertices.” These shortest-paths problems are the topic of this chapter. Not only are shortest-paths problems intuitive for many direct applications, but they also take us into a powerful and general realm where we seek efficient algorithms to solve general problems that can encompass a broad variety of specific applications.