Given a set of edges and an undirected graph, how do I pick the best edge to add to graph to minimize the shortest path?

Question

What I'm thinking is, for each edge in the set of edges I can pick from, build a copy of the graph with that edge inserted into it, then run Dijkstra’s. The best edge will be from the graph with the lowest total weight in the end.

But that seems kind of inefficient. I would have to call Dijkstra for every edge in the set. Is there a better way to do this?

Answer 1

Dirty trick:

Run the Djikstra over modified graph. This graph will include all vertices and edges from the original graph. Twice.
For every vertex i, create a vertex i'. If there was an edge (u,v), create an edge (u',v'). As a result we have two graphs that look the same aside from the 's.
Now comes the magic trick:

• For every shortcut x, y create an edge (x, y').
• Merge target and target'

Running the Djikstra over this graph will give you the shortest path, including shortcuts. Why?

• If the shortcuts don't help for some reasons, we are in the original graph and the result doesn't change.
• If we decide to use a shorcut we are stuck in the copied graph and we can't go back - hence we can use only one shorcut. Since the target is the only "singular" node since we merged it, we can still reach it.

Hence if Djikstra finds a path in this modified graph, we have our new shortest path that takes the shortcuts into the account.

The resulting complexity is given by the Djikstra and since we only added E + len(shortcuts) edges to the mix, nothing changed O-notation wise from the original Djikstra.