Find minimum distance in a graph by adding at most one edge

Problem

Given a weighted directed graph with a source and a destination, you may add at most one extra edge. Find the minimum distance from source to destination.

Constraints

• Weighted, directed graph
• Add at most one additional edge
• Target complexity: O(E * log V)

Approach

• Run Dijkstra from the source, and from the destination on the reversed graph
• For each candidate new edge (u, v): dist_src[u] + w + dist_dst[v]
• Answer is the minimum over the original shortest path and all augmented paths