Finding an edge that decreases the shortest path from A to B by the most

Question

Given an undirected graph G with edge weights, a set of candidate edges (length |V| + |E|), and vertices A and B, find the edge that decreases the shortest path from A to B by the most.

For example:

The candidate edges are the dotted lines. The shortest path from A to B is A -> C -> D -> G -> B (cost 7). But with the edge (D, B), the shortest path is A -> C -> D -> B (cost 6), so the algorithm should return (D, B).

I came up with a brute force solution O((|V| + |E|)^2 log |V|):

• for each candidate edge:
  • add the edge to the graph
  • run Dijkstra's to find the cost of the shortest path from A to B
  • remove the edge
• return the candidate edge that results in the shortest path

but is there anything better?

Answer 1

One approach is:

• Run Dijkstra from A and store distance to each node n in A[n]
• Run Dijkstra from B and store distance to each node n in B[n]
• Loop over each candidate edge. For an edge with weight w that connects vertices x and y, compare w+A[x]+B[y] and w+A[y]+B[x]

The smaller of w+A[x]+B[y] and w+A[y]+B[x] gives the shortest path between A and B when the candidate edge is used.