0 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 algorithms graph-algorithms shortest-path dijkstras-algorithm binary-heap time-complexity + – Bikram 1.9k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 0 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 3 3 Comments reply Harsh181996 commented May 31, 2017 reply Follow flag Sir, I think the running time is O( ( |E| +|V| ) log|V| ) 1 1 replyShare Ahwan commented Aug 4, 2017 reply Follow flag @Bikram sir .. should not it be O( ( |E| +|V| ) log|V| ) ? 0 0 replyShare Bikram commented Aug 4, 2017 reply Follow flag yes, it should be, corrected it , thanks. 0 0 replyShare Please log in or register to add a comment.
0 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 1 1 comment reply Bikram commented Jul 31, 2019 reply Follow flag O ( ( |E|+|V| ) log |V|)... we use adjacency list and binary heap. 0 0 replyShare Please log in or register to add a comment.
