The shortest path problem with resource constraints is a common subproblem when doing column generation. It is often solved with a labeling algorithm. The procedure is very well explained here and here.
To avoid complete enumeration, dominance is crucial. To check if one label dominates another, their resources need to be compared. Hence one is potentially going to check a newly created label against a huge number of other labels. That would imply that having a data structure that stores the labels sequentially in memory to so going through them is efficient as one can benefit for prefetching. However, it would also be beneficial to have the labels stored according to one or more resource, because then one can possibly stop looking for a dominating label early and hence skip many dominance checks. Having them stored makes it necessary to have a data structure that makes random insertion possible and efficient. That does not fit well with having sequential memory. Also, since an unprocessed label might get dominated, it should also be possible and efficient to erase arbitrary labels from the data structure.
Since reconstruction of the optimal path requires that a label store a pointer to the previous label, the pointers also need to stay valid when new labels are added and already existing labels being dominated and deleted.
I realize that a perfect data structure for this is difficult(if not impossible) to make, but what do the state of the art implementations use when doing this?
I use C++ for performance, so references and advice suitable for C++ are welcomed.