Algorithms in a Nutshell

(^164) | Chapter 6: Graph Algorithms
Dense graphs
For dense graphs,Eis on the order of O(V^2 ); for example, in a complete graph of
n=|V| vertices that contains an edge for every pair of vertices, there aren(n–1)/2
edges. Using BELLMAN-FORDon such dense graphs is not recommended, since
its performance degenerates to O(V^3 ). The set of dense graphs reported in
Table 6-3 is taken from a set of publicly available data sets used by researchers
investigating the Traveling Salesman Problem (TSP).We executed 100 trials and
discarded the best and worst performances; the table contains the average of the
remaining 98 trials. Although there is little difference between the priority queue
and dense versions of DIJSKTRA’SALGORITHM, there is a vast improvement in
the optimized DIJSKTRA’SALGORITHM, as shown in the fifth column of the table.
In the final column we show the performance time for BELLMAN-FORDon the
same problems, but these results are the averages of only five executions because
the performance degrades so sharply. The lesson to draw from the last column is
that the absolute performance of BELLMAN-FORDon small graphs seems to be
quite reasonable, but when compared relatively to its peers on dense graphs, one
sees clearly that it is the wrong algorithm to use on these graphs.
Sparse graphs
Large graphs are frequently sparse, and the results in Table 6-4 confirm that one
should use the DIJSKTRA’SALGORITHMwith a priority queue rather than the imple-
mentation crafted for dense graphs; note how the implementation for dense graphs is
10 times slower. The rows in the table are sorted by the number of edges in the
sparse graphs, since that appears to be the determining cost factor in the results.
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
Table 6-3. Time (in seconds) to compute single source shortest path on dense graphs
V E
Dijkstra’s Algorithm
with PQ
Dijkstra’s Algorithm
for DG
Optimized
Dijkstra’s Algorithm
for DG Bellman-Ford
980 479,710 0.0918 0.1147 0.0128 0.2444
1,621 1,313,010 0.2194 0.2601 0.0329 0.7978
6,117 18,705,786 3.6256 4.0361 0.2301 66.0659
7,663 29,356,953 8.3147 8.8592 0.3644 222.3107
9,847 48,476,781 15.2602 16.2169 0.6116 431.2807
9,882 48,822,021 14.7536 16.5594 0.6224 277.8776
Table 6-4. Time (in seconds) to compute single source shortest path on large sparse graphs
V E Density
Dijkstra’s
Algorithm with PQ
Dijkstra’s
Algorithm for DG
Optimized Dijkstra’s
Algorithm for DG
3,403 137,845 2.8 % 0.0453 0.2038 0.098
3,243 294,276 1.2 % 0.017 0.1922 0.1074
19,780 674,195 0.17 % 0.1002 2.9697 1.805
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
Licensed by
Ming Yi