This is a discussion of an STL implementation of Dijkstra's shortest path algorithm utilizing the Standard Template Library (STL) in C++.

The problem Dijksta solved is this: Given an directed weighted graph, find the shortest path from any source node to any target node.

A directed graph is one in which the nodes are connedted by edges that can be traversed in one direction. A weighted graph is one in which traversing an edge has an associated cost. See figure 1 for an example of a weighted directed graph.

In general, Dijkstra's solution is:

• Put the source node into a data structure
• While that data structure is not empty
• Get the next node from the data structure
• Find all nodes reachable from the node retrieved from the data structure
• Keep track of the minimum cost to get to the neighbor nodes
• Keep track of the path needed to get to the neighbor nodes
• Without visiting a node twice, put each of these neighbor nodes into the data struture
  

When this process is complete, if the target node is reachable, we have the minimum cost and path to it.

Naturally, there are an infinite number of ways to code this algorithm. Since the STL is now part of ANSI standard C++, we will take advantage of its containers, algorithms and iterators to produce the actual code.

Several decisions about what containers to use must be made. The primary container is the previously mentioned "data structure". In classical graph theory, either an stack or queue may be used. Using a stack results in a depth-first search while using a queue results in a breadth-first search. (The derivations of these names is easy to see as a stack visits near neighbors last while a queue visits near neighbors first.) However, since we are concerned with minimum cost, we have another option: the STL priority_queue. That is the one we will use. We will make other container decisions later.

By the way, the priority_queue is a slight misnomer. It is actually neither a stack nor a queue. Rather, data is removed based on some cost criterion. See code 1 for several implementaions of a priority_queue.

Next we need a decision on how to store the graph. An adjacency vector will work.

vector<list<int> >av;

Declares a vector of lists. Each vector index represents a node and each list stores neighboring nodes.

However, this does not handle nodes with string names and it does not keep track of cost, visited status nor the current path.

iCarnegie, in its SSD5 course, developed a brillant way to handle all of this information and that is the approach I will use.

A better way is to make a structure or class that does handle this information.

class Node {
public:
   string name;
   list<Edge*> neighbors;
   bool visited;
   int cost;
   Node *back_pointer;
};

We can then store pointers to instances of this class in a container. A container that naturally lends itself to this task is the map. We can use the name string as a key and the pointer as the value:

map<string,Node*> nodemap;

We can then make an edge class that gets stored in the node list neighbors.

class Edge{
public:
   double weight;
   Node * dest;
   Edge(double c,Node *d = NULL):weight(c),dest(d){}
}

See graph.zip for an incomplete (does not do min cost) example implementation.