Introduction to OOP: Chapter 16 : A Case Study : The STL [next] [previous] [audio] [real] [text]

Shortest Path Algorithm

void shortestDistance(const graph & cityMap, 
		const string & start, stringVector & distances)
{
	// process a priority queue of distances to cities
	priority_queue<DistancePair, vector<DistancePair> ,
		greater<DistancePair> > que;
	que.push(DistancePair(0, start));
	
	while (! que.empty()) {
			// pull nearest city from queue
		int distance = que.top().first;
		string city = que.top().second;
		que.pop();
			// if we haven't seen it already, process it
		if (0 == distances.count(city)) {
				// then add it to shortest distance map
			distances[city] = distance;
				// and put values into queue
			stringVector::iterator start, stop;
			start = cityMap[city].begin();
			stop = cityMap[city].end();
			for (; start != stop; ++start) 
				que.push(DistancePair(distance + (*start).second, 
						(*start).first));	
			}
		}
}
Intro OOP, Chapter 16, Slide 19