Dijkstra's Shortest Path Algorithm

[Ganon11]

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:

http://www.cs.umd.edu/~gasarch/651/dijcjacm.pdf

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

[Ganon11]

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!