**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.

Hi, Just read your post. This is nice. I have one question though. The weights are initially defined. Suppose I have an image. I have the start point and end point. I need to find the shortest path from start to end. So what is the weight?

Hi Mizuki, with shortest path problems, the weights between all possible connections in your network will already be known. Unless I misunderstand your question, I don’t see how Dijkstra could be used to find unknown weights.

Hi, Thank you for responding. If I understand you correctly, that’s mean all the pixel values in the image are considered the weights?

Mizuki

I don’t fully understand your problem here. Perhaps you could post or email an explanation of what you are doing? As far as know Dijkstra needs to know all possible weights, since I don’t know how it would manage without unknown values.