Dijkstra's algorithm
Dijkstra's algorithm shortest path algorithm is one of the most commonly used algorithms for finding short distances between two nodes.
This article list down some of the important points for this algorithm and list down some of the useful contents available online.
Important Points
It does not work if the edges have negative weights.
It is used to find shortest path between source and destination in a graph.
Real life uses includes Map, Network communication.
Complexity
The complexity of this algorithm depends on the data structure used.
For a graph G with V vertices and E edges,
For Adjecency Matrix : Complexity is O(V**2)
For Adjecency List and using Priority Queue with O(n) for sorting : O(E + VlogV)
No comments :
Post a Comment
Please leave your message queries or suggetions.
Note: Only a member of this blog may post a comment.