Implementing Dijkstra’s Algorithm using Sedgewick’s C++ Code

Introduction

Dijkstra’s algorithm solves the shortest path problem for a graph with nonnegative edge weights, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms, the k-shortest paths algorithm, for example.

We build a shortest path tree (SPT) one edge at a time, by always taking the next edge that gives a shortest path from the source to a vertex not on the SPT. In other words, we add vertices to the SPT in order of their distance (through the SPT) to the start vertex.

Algorithm Performance

The original Dijkstra’s algorithm did not use min priority queues and was of complexity O(|V|2), where V is the number of vertices. This performance was later improved upon by the use of linked-list representations and min priority queues.

Edges that connect tree vertices to nontree vertices are stored using a priority queue implementation that allows for the updating of priorities.

Implementation of Dijkstra’s Algorithm a la Sedgewick:

This implementation as originally developed by Sedgewick initially finds all shortest paths within the constructor of the SPT template class. Sample code is available here. It uses a priority queue of vertices that are held in order of their distance from the source node to determine all the shortest paths from the source node. The queue is initialized with priority 0 for the source node and priority infinity for the other nodes. The implementation then entyers a loop whereby the lowest-priority node from the queue is moved to the SPT and relax along its incident links:

template <class DenseGRAPH, class Edge> 
class SPT
{ 
private:
	const DenseGRAPH &G;
	vector<double> wt;
	vector<Edge *> spt;

public:

	SPT(const DenseGRAPH &G, int s) : 
		G(G), 
		spt(G.V()), 
		wt(G.V(), 
		G.V())
	{ 
		PQi<double> pQ(G.V(), wt);
	
		for (int v = 0; v < G.V(); v++) pQ.insert(v);
	
		wt[s] = 0.0; 
		pQ.lower(s);  

		while (!pQ.empty()) 
		{ 
			int v = pQ.getmin(); 
			
			if ( v != s && spt[v] == 0 ) return;  
			
			typename DenseGRAPH::adjIterator A(G, v); 
      
			for ( Edge* e = A.beg(); !A.end(); e = A.nxt() ) 
			{ 
				int w = e->w; 
				double P = wt[v] + e->wt;
				
				if (P < wt[w]) 
				{ 
					wt[w] = P; 
					pQ.lower(w); 
					spt[w] = e; 
				}
			}
		}
	}
	
	Edge *pathR(int v) const { return spt[v]; }
	double dist(int v) const { return wt[v]; }
};

Example Usage

Suppose we wish to build the following network:

Then this example is built using the following DenseGRAPH declaration and insert API calls:

typedef DenseGRAPH<Edge> dGraph;
	
dGraph g( 8, true );

g.insert( new Edge( 1, 6, 1.0 ) );
g.insert( new Edge( 1, 2, 2.5 ) );	
g.insert( new Edge( 1, 4, 3.0 ) );	
g.insert( new Edge( 1, 5, 0.5 ) );	
g.insert( new Edge( 2, 1, 0.5 ) );	
g.insert( new Edge( 2, 3, 3.0 ) );
g.insert( new Edge( 2, 4, 2.0 ) );
g.insert( new Edge( 2, 5, 2.5 ) );
g.insert( new Edge( 3, 4, 1.0 ) );
g.insert( new Edge( 3, 7, 1.5 ) );
g.insert( new Edge( 4, 5, 1.0 ) );
g.insert( new Edge( 5, 4, 0.5 ) );
g.insert( new Edge( 5, 6, 0.5 ) );
g.insert( new Edge( 5, 7, 1.5 ) );
g.insert( new Edge( 7, 6, 1.0 ) );

To find all the shortest paths emanating from node 2, for example, then it is a straightforward matter of creating the SPT template class instance, which computes the complete shortest path tree in the constructor. The following code snippet shows how to generate the shortest paths and display the shortest path possible between nodes 2 to 7, which in this case would be 2->1->5->7:

// Find shortest path between nodes 2->7
int source = 2;
int target = 7;
stack<int> path;

SPT<dGraph, Edge> sp( g, source );
			
while ( true )
{
	Edge* e = sp.pathR( target );	
	path.push( target );
	if ( target == source ) break;
	target = e->v;			
}

// Print the path nodes
while ( !path.empty() )
{
	std::cout << path.top() << " ";
	path.pop();
}

Example code implementing Sedgewick’s version of Dijkstra / min priority queues is downloadable from here.