CODEWITHSUNDEEP
algorithmtime-complexitygraph-algorithm
Imago
Imago

Reputation: 501

Dijkstra's Algorithm - complexity

I have a certain problem understanding the complexity of the Djisktra algorithm and hope someone can correct me.

For my example I took a complete graph with n vertices.

You pick a starting vertex, lets say a1, mark it, and then compute all n-1 weights on the edges. O(n)

You pick the smallest one. Let's say vertex a2 and mark it. O(n)

After that you compute n-2 new weights on the edges and look for the next yet unmarked vertex to add your set of marked vertices.

And so on...

The algorithm runs til you could mark all vertices. Complexity: n-1 + n-2 + ... + n - (n - 1) = Binom(n,2) which is in O(n^2), not O(n*ln(n)) what I want.

I read about many many times people use a heap for optimization, however I still don't see how to avoid Binom(n,2) computations.

I have to be wrong at some point, but do not see where.

Upvotes: 4

Views: 1461

Answers (1)

comingstorm
comingstorm

Reputation: 26117

If you have a complete graph, then of course you can't do any better than O(n^2) -- because, that's the size of your input.

If you don't have a complete graph, and are storing your edges in an adjacency list, then you can do better. You still need to look at all your edges, but with a priority queue you can manage O(e + n log n) where e is the number of edges in your adjacency list.

Upvotes: 5

Related Questions