Shortest Path Algorithms with Integer Edge Costs
Tong-Wook Shinn · UC Research Repository (University of Canterbury) · 2002
Single source shortest path algorithms are concerned with finding the shortest distances to all vertices in a graph from a single source vertex. Dijkstra (1959) first came up with an O(n 2 ) algorithm to solve such a problem, where n is the number of vertices 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 possible to improve the underlying data structure of Dijkstra’s algorithm to improve the algorithm’s time complexity to O(m+nlogc).