468,257 Members | 1,429 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,257 developers. It's quick & easy.

Dijkstra's Shortest Path Algorithm

3,652 Expert 2GB
Hey guys,

I'm back, and with another FUN question!

My latest homework asks this question:

"Suppose all the edge weights in a graph are integers between 1 and |E|. How fast can Dijkstra's algorithm be implemented?"

The only thing I could think of is somehow involving bucket sort - since the edges are bounded, we can use bucket sort to achieve an O(n) sorting time - but I'm not sure how I can use the sorted edge weights to help me at all. So I went to the book's reference section at the end of the chapter. There was a reference given that gave the solution to this problem, so I Googled it and came up with this big pdf file:


Basically, this is a portion of a textbook that involves the research done to develop a new data structure called a radix heap that can solve Dijkstra's algorithm in something like O(|E|log(|V|)/|E|log(log(|E|))) time.

I showed this to my T.A., who said there was no way I was expected to come up with this on my own, but hinted that there was some other way I could use bucket sort to improve the running time of DIjkstra's algorithm.

I have no clue of how to do this, so I;d like some guidance if possible.

Note: My class is in C++, but since I don't need to do any coding for this, only understand a concept, I posted in Misc. Discussions. A non-code specific suggestion or hint would be greatly appreciated.

Thanks a lot, guys! I'll continue working here on my end.

Also, the homework is due tomorrow. Haste is also appreciated :D
Nov 14 '07 #1
1 4865
3,652 Expert 2GB
EDIT: wow. Literally 30 seconds after I posted this, I realized something:

At each step in the algorithm, with unbounded edge weights, at least |V|log(|V|) (using a priority queue for fast deleteMin operations). But if the edge weights are bounded, we can sort with Bucket Sort in O(|V|) time and pick the first (smallest) element in O(1) time, which is slightly faster than |V|log(|V|) time.

If anyone else has brilliant suggestions, I'd love to hear them - but crisis averted!
Nov 14 '07 #2

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

6 posts views Thread by ThanhVu Nguyen | last post: by
3 posts views Thread by A_StClaire_ | last post: by
3 posts views Thread by Ook | last post: by
1 post views Thread by arlef | last post: by
2 posts views Thread by Bytter | last post: by
2 posts views Thread by Gurpreet Singh | last post: by
reply views Thread by zattat | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.