Algorithms in a Nutshell

Single-Source Shortest Path | 163

Graph

Algorithms

Figure 6-17. Different executions of Bellman-Ford have the same result

Table 6-2. Time (in seconds) to compute single source shortest path on benchmark graphs

V E

Dijkstra’s

Algorithm

with PQ

Dijkstra’s

Algorithm

for DG

Optimized

Dijkstra’s

Algorithm

for DG Bellman-Ford

6 8 0.01 0.008 0.005 0.005

18 56 0.015 0.016 0.009 0.006

66 464 0.036 0.08 0.042 0.017

258 3,872 0.114 0.71 0.372 0.102

1,026 31,808 1 15.8 9.8 1.8

4,098 258,176 10.5 260.4 155.7 14.3

16,386 2,081,024 51.5 2113.7 1215.6 80.3

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