I've forgot a pair of questions:
Now the solution I propose, since you have a monotonically increasing edge set you can actually compute an incremental solution to the SSSP problem rather than completely re-running Dijkstra. Basically you can patch up the SSSP solution when you do the edge addition in O(N) time (expected time should be much lower but depends on parameters of your graph that I don't have so I won't try to explain in detail). Either way this is either somewhat better, or much better than O(N log N) to re-run Dijkstra. All you do is push the new weight onto the Dijkstra queue and run Dijkstra as normal.
How can I push a weight, if the queue is a vertex queue?
[...] If you really do need concurrent access to the adjacency list then I'd just wrap a readers-writers lock around each vertex's adjacencies.
How can I implement a lock like this? I must to hack the BGL? Or just need to derive from adjacency_list and apply this additional function? Thanks, Cosimo Calabrese.