The state space here is subsets of V, but not all possible subsets and not exponential. The entire state is represented by the priority queue at each step which is bounded by the number of nodes and edges. And each state represented (encoded) by the priority queue transitions to exactly one new state (by popping the top node from the queue and adding the neighbours). And the number of steps is also bounded by the number of edges and nodes in V.

Most importantly, at every step of the algorithm, we only need to preserve the previous node in the state space (the previous state of the priority queue) to compute the new state (pop the top and add the dirty neighbours) and we can forget all previous states that existed before. We don't even need to keep track of the visited nodes, although if we did, that wouldn't change anything.