All Questions
Tagged with heaps shortest-path
3 questions
0
votes
1
answer
3k
views
M + N log N running time for Dijkstra
I'm taking the Design and Algorithms Part -II course in Coursera by professor Tim Roughgarden. In one of the classes, he mentioned that the running time for Dijkstra is $O(m \log n )$ using the heap ...
- 15
4
votes
1
answer
3k
views
Dijkstra without decrease key
I was reading through this paper, "Priority Queues and Dijkstra's Algorithm" by Mo Chen et al., which suggests using Dijkstra's without edge relaxation, but to rather to just insert new ...
- 153
3
votes
3
answers
3k
views
Ideal value of d in a d-ary heap for Dijkstra's algorithm
I stumbled upon the following statement:
By using a $ d $-ary heap with $ d = m/n $, the total times for these two types of operations may be balanced against each other, leading to a total time ...
- 309