Generating Random Test Networks for Shortest Path Algorithms

One of the pillars in the empirical testing of algorithms is the generation of representative and suitably informative test problems. We investigate the particular case of generating random test networks for shortest path problems and discuss several methods proposed for generating such networks. Both analytic and simulation results reveal several pitfalls to avoid in the generation of test networks. We also identify two particular generation methods having desirable characteristics.