446,190 Members | 783 Online
Need help? Post your question and get tips & solutions from a community of 446,190 IT Pros & Developers. It's quick & easy.

# Dijkstra's Shortest Path Algorithm

 Expert 2.5K+ P: 3,652 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 Nov 14 '07 #1