Single-Source Shortest Path (Dijkstra’s Algorithm Implementation in C++)

Suppose you want to fly  a private plane on the shortest path from Saint Johns­ bury, VT to Waco, TX. Assume you know the distances between the airports for all pairs of  cities and towns that are reachable from each other in  one nonstop flight of  your plane. The best-known algorithm to solve this problem, Dijkstra’s Algorithm, finds the shortest path from Saint Johns­ bury to  all other airports, although the search may be halted once the shortest path  to Waco is known.

Dijkstra’s Algorithm conceptually operates in greedy fashion by expanding a set of  vertices, S, for  which the shortest path from s to every vertex VE S is known, but only using paths that include vertices in S. Initially, S  equals the set {s}. To expand S, Dijkstra’s Algorithm  finds the vertex VE V-S whose distance to s is  smallest, and follows v’s edges to see whether a shorter path exists to another  vertex. After processing v2 , for example, the algorithm determines that the distance from s to v3 is  really 17 through the path <s,v2 ,v 3>. Once S  expands to equal V, the algorithm completes.

Input/Output

Input

A  directed, weighted graph G=(V,E) and a source vertex sE V. Each edge e=(u,v) has an associated positive weight in the graph. The quantity n represents the number of  vertices in  G.

Output

Dijkstra’s Algorithm  produces two computed  arrays. The primary result is the array dist[] of  values representing the distance from source vertex s to each vertex in the graph. Note that d ist[ s] is zero. The secondary result is  the array p red [), which can be used to rediscover the actual shortest paths from vertex s to each vertex in the graph.

Assumptions

The edge weights are positive (i.e., greater than zero); if  this assumption is  not true, then dist[u]  may contain  invalid results. Even worse, Dijkstra’s Algorithm will loop forever if a cycle exists whose sum of  all weights is less than zero.

Solution

As  Dijkstra’s Algorithm executes, dis t[v]  represents the maximum length of the shortest path found from the source s to v using only vertices visited within the setS. Also, for  each vES, dist[v] is correct. Fortunately, Dijkstra’s Algorithm does not actually compute and store the setS. It  initially constructs a set  containing the vertices in V, and then it  removes vertices one at a time from the set to compute proper dis t[v] values; for  convenience, we continue to refer to this ever-shrinking set as V-S. Dijkstra’s Algorithm terminates when all vertices are either visited or are shown to not be reachable from the source vertex s.

In the C++ solution shown below, a binary heap stores the vertices in  the set V-S  as a priority queue because, in constant time, one can locate the vertex with smallest priority (where the priority is determined by the vertex’s distance from s). Additionally, when  a shorter  path  from s   to v is found, dist [ v ]   is decreased, requiring the heap to be modified. Fortunately, the decrease Key  opera­tion on  priority queues represented  using binary heaps can be performed  on average in O(log q)  time, where q is the number of verticesin the binary heap, which will always be less than or equal to the number of vertices, n.

//Dijkstra’s Algorithm with priority queue implementation

#include "BinaryHeap.h"
#include "Graph.h"

/** Given directed, weighted graph, compute shortest distance to vertices
* (dist) and record predecessor links (pred) for all vertices. */

void singleSourceShortest(Graph const &g, int s, vector &dist, vector &pred)
{
// initialize dist[] and pred[] arrays. Start with vertex s by setting
// dist[] to 0. Priority Queue PQ contains all v in G.

const int n = g.numVertices( );
pred.assign(n, -1);
dist.assign(n, numeric_limits<int>::max( ));
dist[s] = 0;
BinaryHeap pq(n);

for (int u = 0; u < n; u++)
{
pq.insert (u, dist[u]);
}
// find vertex in ever-shrinking set, V-S, whose dist[] is smallest.
// Recompute potential new paths to update all shortest paths

while (!pq.isEmpty( ))
{
int u = pq.smallest( );
// For neighbors of u, see if newLen (best path from s->u + weight
// of edge u->v) is better than best path from s->v. If so, update
// in dist[v] and re-adjust binary heap accordingly. Compute in
// long to avoid overflow error.

for (VertexList::const_iterator ci = g.begin(u); ci != g.end(u); ++ci)
{
int v = ci->first;
long newLen = dist[u];
newLen += ci->second;

if (newLen < dist[v])
{
pq.decreaseKey (v, newLen);
dist[v] = newLen;
pred[v] = u;
}
}
}
}

Consequences

Arithmetic error also may occur if  the sum of  the individual edge weights exceeds numeric_limits<i n t>: :max () (although the individual values do  not). To avoid this situation, the computed new len uses a long data type.

Analysis

In the implementation of  Dijkstra’s Algorithm, the loop that constructs  the  initial priority  queue  performs  the  insert  operation  V  times, resulting in performance  O(V log V). In   the remaining while loop, each edge is visited once, and thus decrease Key  is called no more than E  times, which contrib­utes O(E log V)  time. Thus, the overall performance is O(( V +E) log V).

The   C++ implementation below is simpler since it avoids the use of  a binary heap. Th e efficiency of   this version is determined by considering how fast the smallest dist [] value in V-S can be retrieved. The while loop is executed n times, since S grows on e vertex at a time. Finding the smallest dist [ u]  in V-S inspects all n vertices. Note that each edge is inspected exactly once in the inner loop within the while loop. Thus, the total running time of  this version is 0 (V 2+E).

//Implementation of Dijkstra’s Algorithm for dense graphs

#include "Graph.h"

void singleSourceShortest(Graph const &graph, int s, vector &dist, vector &pred)
{

// initialize dist[] and pred[] arrays. Start with vertex s by setting
// dist[] to 0.

const int n = graph.numVertices( );
pred.assign(n, -1);
dist.assign(n, numeric_limits<int>::max( ));
vector<bool> visited(n);
dist[s] = 0;

// find vertex in ever-shrinking set, V-S, whose dist value is smallest
// Recompute potential new paths to update all shortest paths

while (true)
{
// find shortest distance so far in unvisited vertices
int u = -1;
int sd = numeric_limits<int>::max( ); // assume not reachable

for (int i = 0; i < n; i++)
{
if (!visited[i] && dist[i] < sd)
{
sd = dist[i];
u = i;
}
}
if (u == -1)
{
break; // no more progress to be made
}

// For neighbors of u, see if length of best path from s->u + weight
// of edge u->v is better than best path from s->v.
visited[u] = true;

for (VertexList::const_iterator ci = graph.begin(u); ci != graph.end(u); ++ci)
{
int v = ci->first; // the neighbor v
long newLen = dist[u]; // compute as long
newLen += ci->second; // sum with (u,v) weight

if (newLen < dist[v])
{
dist[v] = newLen;
pred[v] = u;
}
}
}
}

We can further optimize to remove all  of  the C++ standard template library  objects,  as  shown  below.  By reducing the  overhead of   the supporting classes, we realize impressive performance benefits, as discussed in the “Comparison” section.

/**
* Optimized Dijkstra’s Algorithm for dense graphs
*
* Given int[][] of edge weights in raw form, compute shortest distance to
* all vertices in graph (dist) and record predecessor links for all
* vertices (pred) to be able to recreate these paths. An edge weight of
* INF means no edge. Suitable for Dense Graphs Only.
*/

void singleSourceShortestDense(int n, int ** const weight, int s,int *dist, int *pred)
{
// initialize dist[] and pred[] arrays. Start with vertex s by setting
// dist[] to 0. All vertices are unvisited.
bool *visited = new bool[n];
for (int v = 0; v < n; v++)
{
dist[v] = numeric_limits<int>::max( );
pred[v] = -1;
visited[v] = false;
}

dist[s] = 0;

// find shortest distance from s to all unvisited vertices. Recompute
// potential new paths to update all shortest paths. Exit if u remains -1.
while (true)
{
int u = -1;
int sd = numeric_limits<int>::max( );
for (int i = 0; i < n; i++)
{
if (!visited[i] && dist[i] < sd)
{
sd = dist[i];
u = i;
}
}
if (u == -1)
{
break;
}
// For neighbors of u, see if length of best path from s->u + weight
// of edge u->v is better than best path from s->v. Compute using longs.
visited[u] = true;
for (int v = 0; v < n; v++)
{
int w = weight[u][v];
if (v == u) continue;
long newLen = dist[u];
newLen += w;
if (newLen < dist[v])
{
dist[v] = newLen;
pred[v] = u;
}
}
}
delete [] visited;
}
Advertisements

About Khuram Ali

Programming... Programming and Programming...!!!

Posted on May 3, 2013, in Algorithms, Artificial Intelligence, C++ and tagged , , , , , , , . Bookmark the permalink. 1 Comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: