All Pairs Shortest Path Algorithms
David Cook
Department of Computer Science
University of Canterbury
Abstract
There are many algorithms for the all pairs shortest path problem, depending on variations of the problem. The simplest version takes only the size of vertex set as a parameter. As additional parameters, other problems specify the number of edges and/or the maximum value of edge costs. In this report, we focus on the edge costs. Specifically, we identify the distribution of edge costs. If the spectrum of edge costs distributes around two values, we can speed up the processing time. This is typical in road networks, where we have big distances between main centres, and small distances within the centre cities.
