Test by Bikram | Algorithms | Test 2 | Question: 4

Question

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?

• A. $O (\mid V \mid 2)$
• B. $O (\mid V \mid \log \mid V \mid)$
• C. $O ( ( \mid E \mid+\mid V \mid ) \log \mid V \mid )$
• D. $O( \log \mid V \mid )$

Answer 1

The running time will be O ( ( |E|+|V| ) log |V|) when we use adjacency list and binary heap.

Comments

Sir,

I think the running time is O( ( |E| +|V| ) log|V| )

---

@Bikram sir  .. should not it be   O( ( |E| +|V| ) log|V| )    ?

---

yes, it should be, corrected it , thanks.

Answer 2

@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)

Comments

O ( ( |E|+|V| ) log |V|)... we use adjacency list and binary heap.