Algorithms in a Nutshell

(^156) | Chapter 6: Graph Algorithms
Consequences
Arithmetic error also may occur if the sum of the individual edge weights exceeds
numeric_limits::max( )(although the individual values do not). To avoid
this situation, the computednewLen uses a long data type.
Analysis
In the implementation of DIJKSTRA’SALGORITHMin Example 6-3, the loop that
constructs the initial priority queue performs the insert operationVtimes,
resulting in performance O(VlogV). In the remainingwhileloop, each edge is
visited once, and thusdecreaseKeyis called no more thanEtimes, which contrib-
utes O(E logV) time. Thus, the overall performance is O((V +E) logV).
The fact sheet in Figure 6-15 describes a version of DIJKSTRA’SALGORITHMsuit-
able for dense graphs represented using an adjacency matrix. The C++
implementation found in Example 6-4 is simpler since it avoids the use of a binary
heap. The efficiency of this version is determined by considering how fast the
smallestdist[]value inV–Scan be retrieved. Thewhileloop is executedntimes,
sinceSgrows one vertex at a time. Finding the smallestdist[u]inV–Sinspects all
nvertices. Note that each edge is inspected exactly once in the inner loop within
thewhile loop. Thus, the total running time of this version is O (V^2 +E).
// 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;
}
}
}
}
Example 6-3. Dijkstra’s Algorithm with priority queue implementation (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