I have a weighted, directed graph. I do the following. Given nodes $s$ and $t$ I compute shortest path. Then, I decrease weights of some edges and want to see if there is now another shortest path. Of course, I can recompute shortest path, but I want something faster.
For example, one approach would be to store shortest paths from $s$ to $t$ for every edge in the graph. Then, when I change the weights it takes constant time to check if the shortest path changed (even though, the first step takes much more time). The drawback is that I have to store many paths and to calculate all simple paths in advance, so I'm seeking for alternatives.
So my question is if it's possible to check if the shortest path changed after we decrease edge weights?
Edit: Apparently, this is a problem of dynamic graphs. I didn't delve into the algorithms, so, which algorithm can I use for this problem? I want to improve on running time Dijkstra algorithm.