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?.

  • 5
    $\begingroup$ Fibonacci heap. $\endgroup$ – PSPACEhard Oct 23 '16 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 '16 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 '16 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 '16 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.