HP Integrity NonStop H-Series - Manual (Page 105)

cityMap[pensacola][phoenix] = 5;
cityMap[peoria][pittsburgh] = 5;
cityMap[peoria][pueblo] = 3;
cityMap[phoenix][peoria] = 4;
cityMap[phoenix][pittsburgh] = 10;
cityMap[phoenix][pueblo] = 3;
cityMap[pierre][pendleton] = 2;
cityMap[pittsburgh][pensacola] = 4;
cityMap[princeton][pittsburgh] = 2;
cityMap[pueblo][pierre] = 3;
The type stringVector is a map of integers indexed by strings. The type graph is, in effect, a
two-dimensional sparse array, indexed by strings and holding integer values. A sequence of
assignment statements initializes the graph.
A number of classic algorithms can be used to manipulate graphs represented in this form. One
example is Dijkstra's shortest-path algorithm. Dijkstra's algorithm begins from a specific city given as
an initial location. A
priority_queue of distance/city pairs is then constructed, and initialized with the
distance from the starting city to itself (namely, zero). The definition for the distance pair data type is
as follows:
struct DistancePair {
unsigned int first;
string second;
DistancePair() : first(0) { }
DistancePair(unsigned int f, const string & s)
: first(f), second(s) { }
};
bool operator < (const DistancePair & lhs, const DistancePair & rhs)
{ return lhs.first < rhs.first; }
In the algorithm that follows, note how the conditional test is reversed on the priority queue, because
at each step we wish to pull the smallest, and not the largest, value from the collection. On each
iteration around the loop we pull a city from the queue. If we have not yet found a shorter path to the
city, the current distance is recorded, and by examining the graph we can compute the distance from
this city to each of its adjacent cities. This process continues until the priority queue becomes
exhausted.
void shortestDistance(graph & cityMap,
const string & start, stringVector & distances)
{
// process a priority queue of distances to cities
priority_queue,
greater > que;
que.push(DistancePair(0, start));
while (! que.empty()) {
// pull nearest city from queue
int distance = que.top().first;