Dijkstra's Algorithm - complexity

Question

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.

What is n and why do you have to do something n times at each vertex? — n. m. could be an AI
– n. m. could be an AI, Commented Mar 23, 2016 at 18:19

comingstorm · Accepted Answer · 2016-03-23 18:27:07Z

5

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.

edited Mar 23, 2016 at 18:27

answered Mar 23, 2016 at 18:22

comingstorm

26.2k3 gold badges47 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Imago Over a year ago

Ah ok. This really frustrated me, because in all literature I read only about your stated O(E+ n + log n) and this really confused me. I have to check how the priority queue is used. Thank you for your answer.

Erick G. Hagstrom Over a year ago

Complete or not, you still get O(e + n log n). It's just that when the graph is complete, e = n^2, giving O(n^2 + n log n) = O(n^2).

Collectives™ on Stack Overflow

Dijkstra's Algorithm - complexity

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related