Experimental analysis of shortest paths algorithms

Shortest paths problem is one of the most encountered graph problems, which is commonly solved as subroutine in large variety of other, more complex tasks. If some algorithm or implementation fits the specific purpose, may, or may not, be completely obvious in practice. In some instances, theoretically correct solution behaves poorly in practice, lacking by more than order of magnitude after concurrent solution. Main goal of thesis, is to provide up to date overview of current algorithms, extended by experimentally obtained data and guidelines for their best usage. Majority of listed algorithms was tested on the same system, to provide wide and consistent comparison. Mainly, listed algorithms belongs to class SSSP, and are implementable to commodity hardware. Algorithms belonging to other classes, like OPSP or APSP are also mentioned. Special attention is dedicated to current growth of parallelism on hardware side, such as multi-core CPUs and massively parallel computing environments derived from GPU