Abstract for HONS 01/99 - Computer Science and Software Engineering - University of Canterbury - New Zealand
HONS 01/99

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.

  • Phone: +64 3 364 2362
    Fax: +64 3 364 2569
    admin@cosc.canterbury.ac.nz
  • Computer Science and Software Engineering
    University of Canterbury
    Private Bag 4800, Christchurch
    New Zealand
  • Follow us
    FacebookYoutubetwitterLinked In