We are the first to study the problem of refreshing a cache in a changed graph.
A bitmap-based cache structure is designed to store shortest paths.
Three algorithms are developed to detect affected shortest paths.
Four refreshment strategies are proposed to update a cache efficiently.
Extensive experiments on real data sets show the efficiency of our algorithms.