Abstract for HONS 09/02 - Computer Science and Software Engineering - University of Canterbury - New Zealand
HONS 09/02

Shortest Path Algorithms with Integer Edge Costs

Tong-Wook Shinn
Department of Computer Science and Software Engineering
University of Canterbury

Abstract

Single source shortest path algorithms are concerned with finding the shortest dis- tances to all vertices in a graph from a single source vertex. Dijkstra (1959) first came up with an O(n2 ) algorithm to solve such a problem, where n is the number of ver- tices in the graph. If the given graph has a special property that all edge costs within the graph are integers and these edge costs are bounded by some constant c, it is pos- sible to improve the underlying data structure of Dijkstra’s algorithm to improve the algorithm’s time complexity to O(m + n logc).

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