673 views

1 Answer

1 votes
1 votes
after analysis on this i found.

1) yes but they all infinite distance apart from source.

2)yes  as mentioned in algorithm while(Q!=phi) dijkstra's will always terminate

3)yes because for each vertex call extract min which is take O(log v) i.e total O(v log v) and in that for each edge we have relax all the adjacent edge which internally call decrease function call which take O(log v) i.e for each edge relaxation will be done only once so tatal for this O(e logv)

so total time O((v+e)logv) but in worst case there may be chance that no relaxation performed in that case time O(vlogv +e).

4)when no relaxation will performed in that case all vertices have cost infinity so simply extract one of them

Related questions

6 votes
6 votes
1 answer
1
vaishali jhalani asked Nov 5, 2016
2,996 views
What is the time complexity of Dijkstra’s algorithm if it is implemented using AVL Tree instead of Priority Queue over a graph G = (V, E)?
1 votes
1 votes
1 answer
2
vaishali jhalani asked Nov 4, 2016
1,049 views
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?
0 votes
0 votes
1 answer
3
Chandra Bhushan Kuma asked Dec 19, 2015
278 views
if all edge in the graph have distinct weight the the sortest path between two vertex is unique?/