Complexity of Prims Algorithm using Priority Queue?

algorithm, java, minimum-spanning-tree, prims-algorithm

Solution

If you use a Fibonacci heap, then extracting the min is `O(lg V)` amortized cost and updating an entry in it is `O(1)` amortized.

If we use this pseudo code

while priorityQueue not empty
    u = priorityQueue.exractMin()
    for each v in u.adjacencies
        if priorityQueue.contains(v) and needsWeightReduction(u, v)
            priorityQueue.updateKeyWeight(u, v)

Assume that the implementation has constant time for both `priorityQueue.contains(v)` and `needsWeightReduction(u, v)`.

Something to note is that you can bound slightly tighter for checking adjacencies. While the outer loop runs `V` times, and checking the adjacencies of any single node is at worst `V` operations, you can use aggregate analysis to realize that you will never check for more than `E` adjacencies(because theres only E edges). And `E <= V^2`, so this is a slightly better bound.

So, you have the outer loop V times, and the inner loop E times. Extracting the min runs `V` times, and updating an entry in the heap runs `E` times.

  V*lgV + E*1
= O(V lgV + E)

Again, since `E <= V^2` you could use this fact to substitute and get

  O(V lgV + V^2)
= O(V^2)

But this is a looser bound when considering sparse graphs(although correct).

Problem

I am using an adjacency matrix, priority queue is the data structure. By my calculation, complexity is `V^3 log V`: - While loop: `V` - Checking adjacent Vertices: `V` - Checking the queue if the entry is already present, and updating the same: `V log v` But, I read everywhere that the complexity is `V^2` Please explain.

Original source