1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.