CODEWITHSUNDEEP
algorithmdata-structuresgraph-algorithmdijkstra
Abhishek Patel
Abhishek Patel

Reputation: 615

Time Complexity of Dijkstra's Algorithm when using Adjacency Matrix vs Adjacency Linked List

For a graph with v vertices and e edges, and a fringe stored in a binary min heap, the worst case runtime is O((n+e)lg(n)). However, this is assuming we use a adjacency linked list to represent the graph. Using a adjacency matrix takes O(n^2) to traverse, while a linked list representation can be traversed in O(n+e).

Therefore, would using the matrix to represent the graph change the runtime of Dijkstra's to O(n^2lg(n))?

Upvotes: 3

Views: 2905

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59303

The O(log n) cost is paid for processing edges, not for walking the graph, so if you know the actual number of edges in the graph then Dijkstra's algorithm on an adjacency matrix with min-heap is within O(n^2 + (n+e)log(n)) time.

Upvotes: 2

Related Questions