Shortest Path Algorithm

Here then is a typical algorithm we might use on our graph. It uses Dijkstras algorithm to determine the shortest distance to each city from a given starting point. I won't go over the details, but the current best distances are kept in a priority queue, which is ordered by the smallest distance. At each step we pull the smallest value out of this queue, and if it represents a city we have not yet visited, we save the distance (which must be the sortest distance to this city), and enter into the priority queue all the cities that can be reached from this new city.

The algorithm makes use of many different data structures from the STL, such as a map, a vector, a string, and a priority queue.

[audio] [real] Text to accompany slide19, in Chapter 16 of An Introduction to Object-Oriented Programming