Efficient traversal of a shortest path tree in BFS order with arbitrary nodes

Efficient traversal of a shortest path tree in BFS order with arbitrary nodes

I need to traverse the shortest path tree (generated from the Dijkstra's
algorithm) of a graph, so I can perform some operations on its nodes in
BFS order. My first thought was an algorithm like this:
init a queue Q
enqueue the root node of the SP tree and mark it
while the queue is not empty:
dequeue the last element (node) of Q and perform operations
search into the set of graph nodes for nodes who have the above node as a
predecessor
enqueue each of them in Q
Then, I realized that the 'search' procedure will add too much extra
execution time, as i should perform this algorithm to large road networks,
modelled as graphs.
One way to make this some more efficient, is to use a vector of void*
elements field in my node's struct, so I can store there the direct
successors of each node when the SP tree is generated. My node's struct
will be like:
struct node: DefaultGraphItem
{
node(): id(0), x(0), y(0),
dist(std::numeric_limits<unsigned int>::max()),
pqitem(0), pred(0), timestamp(0)
{}
unsigned int id;
unsigned int x, y;
unsigned int pqitem;
void* pred;
std::vector<void*> TDSPsucc; //Vector of direct successors of this node in
TDSP tree.
unsigned int timestamp;
};
I started taking this approach, but I faced implementation issues, like
the insertion of a popped vector element into the queue.
I will appreciate any help on implementation or a suggestion of a better
algorithmic technique.