in Algorithms
553 views
5 votes
5 votes

in Algorithms
by
553 views

1 comment

not visible
0
0

1 Answer

1 vote
1 vote
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
by

1 comment

Great Explanation sir !
0
0

Related questions