Algorithms in a Nutshell

Single-Source Shortest Path | 159

Graph

Algorithms

Variations

Ifashortestflightpathhasmanyhops,youmightbesolvingthewrongproblem.

Forexample,iftheintentwastoreducegasconsumption,aninitialhypothesisis

that the shortest path would be the way to go. However, one must factor in the

gasconsumedinlandingandtakingoff.You’dfigureouttheextrafuelconsump-

tioninalandingand take-offand convertthistotheequivalentdistance(say,D)

you’d have to fly in order to consume this much fuel. You then addDto the

distance between each pair of airports and find the shortest path in the modified

problem.

int *dist, int *pred) { /* out */

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

}

Example 6-5. Optimized Dijkstra’s Algorithm for dense graphs (continued)

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