Algorithms in a Nutshell

(^162) | Chapter 6: Graph Algorithms
Benchmark data
It is difficult to generate “random graphs.” In Table 6-2, we show the perfor-
mance on graphs withV=k^2 + 2 vertices andE=k^3 – k^2 +2kedges in a highly stylized
graph construction (for details, see the code implementation in the repository).
Note that the number of edges is roughlyn1.5wherenis the number of vertices in
V. The best performance comes from using the priority queue implementation of
DIJSKTRA’SALGORITHMbut BELLMAN-FORDis not far behind. Note how the
variations optimized for dense graphs perform poorly.
Figure 6-16. Bellman-Ford fact sheet
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