I don't really understand how we can use the fact that the edge weights are integers in the range [1, 2, ... , C] in order to speed up the computation of Dijkstra's algorithm. I read this lecture but I still don't really get it. I understand why we make an array of size |V|C + 1 holding buckets where we put nodes with length i in bucket i. But from that point on I can't really wrap my head around how it'd help us solve it any faster.

I suppose we start off with putting the startnode s in the 0:th bucket and then putting its neighbors in their respective buckets, but that's just the normal algorithm. How does it change from there?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.