Will adding a single edge to a given graph create a new shortest path?

Assume I have a directed graph with a start node A and an end node C, and I already know that the shortest path from A to C in this graph is of length n and uses nodes A, B0,B1, ..., Bn-2, C.

I want to know whether adding a given new edge to this graph will create a new shortest path from A to C of length < n. Of course, I could simply use Dijkstra's algorithm to check the shortest path in this new graph, but my question is whether the information we have about the shortest path in the graph without this new edge can somehow be used to solve this problem more efficiently?


You add a new edge (u,v), you need to check if the triangular inequality holds:

d(v) < d(u) + w(u,v)

If it does, there is no new shortest path.

Otherwise, you have a new shortest path from the source (A) to v, which invalidates all shortest paths with weight greater than the new d(v).


 ? Modified Shortest Path Algorithm (Dijkstra's)
 ? Find the set of all possible paths from the source to destination covering all edges
 ? Perform Group Action using MapReduce
 ? Perform Group Action using MapReduce
 ? Perform Group Action using MapReduce
 ? count average of number using Hadoop/Mapreduce
 ? How to perform reduce side join on Java Mapreduce with two table which have many-to-many relationship?
 ? How to solve TOP 'n' FOR EACH 'entity' in MapReduce?
 ? Mapreduce tasks not running in parallel in pseudodistributed hadoop
 ? How to design a special MapReduce inverted index?