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 data structure where $m$ is the number of edges and $n$ is the number of vertices. Also, he mentioned that using an exotic type of heap data structure the running time can be improved to $O(m + n \log n)$. I googled and couldn't find any relevant answers. It would be much helpful to know such data structures as its running time would be blazingly fast. Can anybody help?
$\begingroup$
$\endgroup$
9
-
1$\begingroup$ Maybe he meant en.wikipedia.org/wiki/Fibonacci_heap ? $\endgroup$– nir shaharCommented Jun 8, 2021 at 16:26
-
$\begingroup$ As @nirshahar has stated, Fibonacci heaps are a way to improve the time complexity. however, as stated in the article, they are not "blazingly fast", only asymptotically faster (and difficult to implement). $\endgroup$– NathanielCommented Jun 8, 2021 at 16:54
-
$\begingroup$ @nirshahar . Seems like it. because the article says the fibonacci heap's worst case time complexity is O(a + b log n) where a = number of inserts, b = number of deletions, n = max size of heap. Here we would be inserting m number of edges into the heap and would do a deletion during each iteration which sums to n number of deletions and max size is the number of heap. In our case the maximum size is m - the number of edges. The last part is the only place where it seems different. By the definition it becomes O(M + N Log M). Anyway thanks. Will check whether modifications can be done. $\endgroup$– Veera KumarCommented Jun 8, 2021 at 17:05
-
$\begingroup$ @nirshahar I think the as there could be a maximum of quadratic number of edges in graphs corresponding to the number vertices. Thus m=n^2. Thus applying this in the time complexity found reduces O(M + N log M) => O(M + N Log N ^ 2) => O(M + 2 * N Log N) => O(M + N log N). $\endgroup$– Veera KumarCommented Jun 8, 2021 at 17:10
-
$\begingroup$ @Nathaniel thanks for information. Does Dijkstra's shortest path practically run faster in Fibonacci heap than using binary heap or is it slower ? How do they differ in Sparse and Dense graph. you have any suggestion ? $\endgroup$– Veera KumarCommented Jun 8, 2021 at 17:26
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
Thanks to @nirshahar for pointing out the data structure is Fibonacci heap with a worst case running time of O(a + b log n) where a = number of inserts, b = number of deletions, n = maximum size of the heap. For Dijkstra's algorithm for shortest path we have to insert M number of edges initially followed by n number of deletions in each iteration. Hence it worst case is O(m + n log m). In worst case for a dense graph m = n^2. Thus the worst case running time is transformed to O(m + n log n).