Dijkstra's Algorithm - Complexity

Question

I have a specific problem that understands the complexity of the Djisktra algorithm and hope someone can fix me.

In my example, I took a complete graph with n vertices.

You pick the starting vertex, let's say a1, mark it, and then calculate all the weights n-1 around the edges. O (n)

You choose the smallest. Let say the vertex a2 and mark it. O (n)

After that, you calculate n-2 new weights at the edges and look for the next, but unmarked vertex, to add your set of marked vertices.

Etc...

The algorithm runs until you have checked all the vertices. Difficulty: 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 many times when people use a bunch for optimization, however I still don't see how to avoid Binom (n, 2) calculations.

I must be wrong at some point, but I don’t see where.

Answer 1

If you have a complete schedule, then of course you cannot do anything better than O (n ^ 2), because the size of your input.

If you do not have a complete schedule and your edges are stored in the adjacency list, then you can do better. You still need to look at all your edges, but with priority queue you can control O (e + n log n), where e is the number of edges in the adjacency list.