Question about Prims algorithm where weights are between 1 and some constant W

Question

I came across a couple of solutions to one of the problems that is in the CLRS textbook (pg. 637 23.2-5 edition 3). I am wondering if anyone can make a clarification as to the stated running time of the solution.

Q: Given that we know the edge weights on a graph are between $1$ and some constant $W$, how fast can we make Prim's algorithm run?

Solution:

• Uses an array of linked lists where each index corresponds to a given weight [$1\dots W + 1$]
• Each link linked lists contains a series of vertices with the weight of the index as their key

The run time given is $O(E)$

They break it down as follows:

$O(1)$ to find the vertex with smallest weight - I understand this part since we scan at most $W$ array slots to find a non-empty list and $W$ is constant.

$O(1)$ for decrease key - This makes sense as far as the actual removing of a link from one list and inserting it into another

My question is about the decrease key step. Say for example we pull the node $A$ from the 3rd slot, that is the next node to be processed. We look at $A$'s adjacency matrix and see that it has edges to $B, C, F$. Since we are using linked lists we have no choice other than to look at all array slots from $4$ to $W$ and see if we can find the vertices listed in the linked list for that particular index. Then delete the vertex from its current list and add it to the correct list if we find it. Possible search time = $O(V)$ [since we store vertices in the linked lists and could search all before finding our desired vertex] not $O(1)$.

Since each decrease key takes $O(V)$ and we process all vertices running time = $O(V^2)$.

If anyone could let me know where I am going astray in my analysis I would greatly appreciate it.

Answer 1

The solution is to preprocess the adjacency matrix so that each vertex now has a list of adjacent vertices. When decreasing keys, you address each edge at most twice, so this part of the algorithm runs in $O(E)$.

The basic observation here is that you can implement a priority queue in $O(W)$ if the number of different weights is $W$. You have to be careful to maintain an array mapping the vertices to their current location in the priority queue, but then all operations are indeed $O(W)$.