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?
- 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.