I am implementing a complex shortest path algorithm for large graphs in C++.

This algorithm basically constructs a hierarchy of shortcut graphs by utilizing nice properties.

The first step in the algorithm to construct a shortcut graph G[i] is to determine its vertex set C[i]. I have no problem with this. The second step involves adding edges to the shortcut graph by following certain rules:

there is an edge between a pair of nodes u,v of C[i] iff the shortest path from u to v in the original graph G does not contain another node of C[i] and if its length is no more than r.

At each level i of the hierarchy, the bound r is equal to 8^i. To compute the shortest paths between all node pairs u,v in C[i], I simply use Dijkstra bounded at r, which works successfully. Ideally, I guess that it would be nice to save the results from a level i’s Dijkstra search in order to start the search at the next level with existing information.

Due to the fact that the graphs are huge and that the distances map computed by this Dijkstra contains a bit more information than just {reached_node: distance} for other requirements of my algorithm, I assumed that it would be pointless to try and keep the returned value of Dijkstra and pass it to the next level.

But after thinking about it again and calculating that my distances map contains:

• 32-bit int for keys (reached nodes)
• 64-bit double for the distances, which I realise now that I could probably reduce to floats
• 64-bit double for another distance measure useful for my algorithm
• 32-bit parent to be able to find the path between the source and this node using the map
  I realise that for graphs of e.g. 10M nodes, this is 228MB, which is considerable but definitely manageable, given that we don’t need to store them after the next shortcut graph is complete. So I want to try and see if it works.

So my question is: are there any considerations to take into account if I initialize Dijkstra’s algorithm with a distances map such as {source:0, other_nodes:infinity|existing_distance} and a priority queue that contains all the existing reached nodes and distances ?

In my understanding, the search wouldn’t push any element to the queue until it reaches the end of the search space of the previous search, but then it would simply “resume” normally.

I am just not sure if this is correct, or if it breaks the correctness of Dijkstra’s algorithm.

I have tried on small hand-made input graphs that I could manually run the algorithm on, but I am not confident enough to affirm that it works on all graphs (by all graphs, I mean those that a regular Dijkstra could work on, of course).