## Discussion Forum

Que. | What will be the running-time of Dijkstra's single source shortest path algorithm, if the graph G(V,E) is stored in form of adjacency list and binary heap is used − |

a. | Ο(|V|2) |

b. | Ο(|V| log |V|) |

c. | Ο(|E|+|V| log |V|) |

d. | None of these |

Answer:Ο(|E|+|V| log |V|) |

Hayat :(May 04, 2020)
What will be the time complexity of this algorithm,which is given below
DIJKSTRA (G, w, s) 1. INITIALIZE-SINGLE-SOURCE (G, s) 2. S=0 3. Q=G. V 4. while Q not equal to 0 5. EXTRACT-MIN(Q) 6. S = S union {u} 7. for each vertex v belong G. Adj[u] 8. Relax (U, v, w) |

Click to Add Comment |