> You come up with some topological order of states in abstract state-space
If the state space is "subsets of V", then it's exponentially larger than the set of states actually visited in Dijkstra's algorithm. Dijkstra's algorithm has an invariant that the vertices visited have a smaller distance than the vertices not visited. For vertex sets that adhere to this invariant, there's clearly a topological order, but for arbitrary subsets of V I don't see how this topological order would be defined.
I guess my gripe is that in my view, the framework of dynamic programming is not a useful way to analyze algorithms that explore a small set of states in an exponentially larger state space.
I think what you're missing is that DP is not an algorithm in itself, but rather a theorem. I also didn't knew about this for a long time. Quoting from [1, §4]
> It should be stressed, here and elsewhere, that the DP functional equation
> does not constitute an algorithm. It merely stipulates a certain property
> that function f defined in (3) must satisfy. Indeed, in the context of Theorem
> 2 the functional equation constitutes a necessary optimality condition. This
> point is sometime not appreciated by students in their first encounter with DP
so that is actually happening in Dijkstra's algorithm is that the DP optimality condition is being reached with a sequence of clever approximations. Another common way to reach the DP optimality condition is by recursively exploring everything with a cache, this is how compsci people usually learn about DP, and of course this can get exponential and does not apply well to big problmems. Though, both are dynamic programming at their core.
> in my view, the framework of dynamic programming is not a useful way to analyze algorithms that explore a small set of states in an exponentially larger state space
Well, since DP is a theorem I kinda agree, it is not how one should think about it when solving day-to-day problems. But formally DP is the reason why these algorithms work in the first place.
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.
If the state space is "subsets of V", then it's exponentially larger than the set of states actually visited in Dijkstra's algorithm. Dijkstra's algorithm has an invariant that the vertices visited have a smaller distance than the vertices not visited. For vertex sets that adhere to this invariant, there's clearly a topological order, but for arbitrary subsets of V I don't see how this topological order would be defined.
I guess my gripe is that in my view, the framework of dynamic programming is not a useful way to analyze algorithms that explore a small set of states in an exponentially larger state space.