0 votes 0 votes What will be the running-time of Dijkstra's single source shortest path algorithm, if the graph $G(V,E)$ is stored in the form of an adjacency list and binary heap is used? $O (\mid V \mid 2)$ $O (\mid V \mid \log \mid V \mid)$ $O ( ( \mid E \mid+\mid V \mid ) \log \mid V \mid )$ $O( \log \mid V \mid )$ Algorithms tbb-algorithms-2 + – Bikram asked May 26, 2017 • edited Aug 20, 2019 by Counsellor Bikram 1.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 0 votes 0 votes The running time will be O ( ( |E|+|V| ) log |V|) when we use adjacency list and binary heap. Bikram answered May 26, 2017 • selected Jul 31, 2019 by Bikram Bikram comment Share Follow See all 3 Comments See all 3 3 Comments reply Harsh181996 commented May 31, 2017 reply Follow Share Sir, I think the running time is O( ( |E| +|V| ) log|V| ) 1 votes 1 votes Ahwan commented Aug 4, 2017 reply Follow Share @Bikram sir .. should not it be O( ( |E| +|V| ) log|V| ) ? 0 votes 0 votes Bikram commented Aug 4, 2017 reply Follow Share yes, it should be, corrected it , thanks. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes @Bikram sir, please help as we know Dijkstra's take O(ElogV) and as it is linklist implentation it will be sparks graph E is O(V) so answer should be O(Vlog V) crazysarth answered Jul 30, 2019 crazysarth comment Share Follow See 1 comment See all 1 1 comment reply Bikram commented Jul 31, 2019 reply Follow Share O ( ( |E|+|V| ) log |V|)... we use adjacency list and binary heap. 0 votes 0 votes Please log in or register to add a comment.