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).
