Algorithms in a Nutshell

Single-Source Shortest Path | 161

Graph

Algorithms

Intuitively BELLMAN-FORDoperates by makingnsweeps over a graph that check

to see if any edge (u,v) is able to improve on the computation fordist[v]given

dist[u]and the weight of the edge over (u,v). At leastn–1 sweeps are needed, for

example, in the extreme case that the shortest path fromsto some vertexvgoes

through all vertices in the graph. Another reason to usen–1 sweeps is that the

edges can be visited in an arbitrary order, and this ensures that all reduced paths

have been found. Indeed, visiting edges in a different order leads to a different set

of computations that reduce thedist[]values. Figure 6-17 shows two executions

of BELLMAN-FORDon two graphs whose only difference is the labeling of vertices

v 1 andv 4. Both executions nonetheless arrive at the same result, if you consider

the relabeling.

BELLMAN-FORDis thwarted only when there exists a negative cycle of directed

edges whose total sum is less than zero. To detect such a negative cycle, we

execute the primary processing loopntimes (one more than necessary), and if

there is an adjustment to somedist[]value, a negative cycle exists. The perfor-

mance of BELLMAN-FORD isO (V*E), as clearly seen by the nested loops.

Comparison

The following list compares the expected performance of the three algorithms by

computing a rough cost estimate:

•BELLMAN-FORD: O(V*E)

•DIJKSTRA’SALGORITHM for dense graphs: O(V^2 +E)

•DIJKSTRA’SALGORITHM with priority queue: O((V+E)*log V)

We compare these algorithms under different scenarios. Naturally, to select the

one that best fits your data, you should benchmark the implementations as we

have done. In the following tables, we execute the algorithms 10 times and

discard the best and worst performing runs; the tables show the average of the

remaining eight runs.

for (int u = 0; u < n; u++) {

for (VertexList::const_iterator ci = graph.begin(u);

ci != graph.end(u); ++ci) {

int v = ci->first;

long newLen = dist[u];

newLen += ci->second;

if (newLen < dist[v]) {

if (failOnUpdate) { throw "Graph has negative cycle"; }

dist[v] = newLen;

pred[v] = u;

leaveEarly = false;

}

}

}

if (leaveEarly) { break; }

}

}

Example 6-6. Bellman-Ford algorithm for single source shortest path (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