On Wed, May 14, 2014 at 11:14 AM, Sensei <senseiwa@gmail.com> wrote:

Sincerely, I don't know what I should cache. My initial thought is creating a hashmap with key being the source node, and value something that allows me to easily retrieve the path.

What do you think I need to cache? Does it suffices to have a map from node index (std::size_t) to the node's predecessor map?

A simple way to do it would be to use an associative container with both source and destination as key, and the full path as value.

I did this before (not with boost graph though) and it was enough for my case, but if you want smarter cache that might be more complicated.