469 views

2 Answers

0 votes
0 votes
The total time complexity of Dijkstra’s Algorithm is given by : E.T(update key / relaxing edges) + V.T(to delete min) .
Where E is the edge and V denotes the vertices. T represents the time to implement the operation given in parenthesis.

The minimum in a sorted array is present at the first position itself (I am assuming an ascending sorted array) hence  the time is O(1) . Whereas the time required to update the key will be O(V). [The number of vertices in the array.]

Therefore we get the time as V+EV which can be taken as EV.

Please correct me If I am wrong.

Related questions

0 votes
0 votes
0 answers
1
Abhisek Tiwari 4 asked Nov 28, 2018
178 views
Dijkstra Algo terminates and produce wrong result when graph contain negative wt CycleWhat about Belman Ford??and FloydWarshall???
0 votes
0 votes
0 answers
2
OneZero asked Nov 28, 2018
354 views
Prove dijkstra’s algorithm using Heap is O((n+|E|)logn) where n is no.of vertices and |E| is number of edges?Book : Fundamentals of Computer Algorithms By sahni pa...
0 votes
0 votes
1 answer
3
adeemajain asked Nov 17, 2018
260 views
Will dijkistra fail if a graph has negative weight cycle which is unreachable from source????
0 votes
0 votes
1 answer
4
Vipin Rai asked Nov 11, 2018
666 views
What is the difference between Dijkstra and Bellman Ford algorithm?Will the shortest path given by both be same in following conditions :a) All positive edge weightsb) So...