Dijkstra's algorithm on a graph whose edge weights are limited

2
votes

Suppose we want to run Dijkstra's algorithm on a graph whose edge weights are integers in the range {1,2,...,W}, where W is a relatively small number. How to find the shortest path from vertex s to t in O((|V|+|E|)logW)?

I encountered this problem from the book Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani. I could prove that if we implement the Dijkstra's algorithm as before, at each iteration the range of the distances for nodes in the priority queue would be within W. However, since priority queues do not have the property to put elements with same weights into the same bucket, this observation does not directly lead to a solution to the problem.

Could anyone give me some hints on how to go one step further to make the bounded range W work for me?

Thanks!

1
algorithmdijkstra
Hmmh, probably the sorting of the priority queue could be faster via counting/radix sort. Also updating (remove+insert) an element could now be faster as the queue could be an array of arrays (or sorted map of arrays) - Karussell
The solution is given (the Bounded Integer Edge Weights problem) in the lecture Courses.MIT. Furthermore, its time complexity is $O(|V| + |E|)$ in linear. - hengxin

1 Answers

1
votes

How many different numbers you can have in your priority queue?

Solution Note that after you extract the node with size X(and now you relax..) the max size it can reach is X+W. all the other numbers are bigger then X (because you took the min from the queue) so you have only O(W) different numbers in the queue,so you can use it as a binary heap and then every step will took O(logW) and all together will be: (V+E)logW.