1
$\begingroup$

We all know about the djikstra's algorithm for computing single source shortest path and the complexity for the same as O(m log n) ( m being the number of edges and n the number of vertices ), this complexity results from using the heap as a data structure for the algorithm

However I recently came across a statement which says this complexity can be improved to O( m + n log n) by using another exotic type of heap as a data structure. Does anyone has any idea about this data structure which is being mentioned?.

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ Fibonacci heap. $\endgroup$
    – PSPACEhard
    Oct 23, 2016 at 8:09
  • 2
    $\begingroup$ Since even Wikipedia has answers both here and here, I think you did not do enough research before asking here. Does your question go beyond what is written there? $\endgroup$
    – Raphael ♦
    Oct 23, 2016 at 10:22
  • $\begingroup$ @Raphael wasn't sure where to start i was mostly following djikstra's algorithm however these comments should get me started . Thanks. $\endgroup$
    – Shubham Singh rawat
    Oct 23, 2016 at 12:29
  • $\begingroup$ I do believe @NP-hard should have marked his comment as an aswer since that is the correct answer. See: en.wikipedia.org/wiki/Dijkstra%27s_algorithm $\endgroup$
    – Carlos Linares López
    Oct 24, 2016 at 12:40

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.