Algorithms in a Nutshell

Single-Source Shortest Path | 157

Graph

Algorithms

We can further optimize Example 6-4 to remove all of the C++ standard template

library objects, as shown in Example 6-5. By reducing the overhead of the

supporting classes, we realize impressive performance benefits, as discussed in the

“Comparison” section.

Example 6-4. Implementation of Dijkstra’s Algorithm for dense graphs

#include "Graph.h"

void singleSourceShortest(Graph const &graph, int s, /* in */

vector<int> &dist, vector<int> &pred) { /* out */

// 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;

}

}

}

}

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use