Minimum Cost Path with Edge Reversals

Minimum Cost Path with Edge Reversals

What is this problem about?

The Minimum Cost Path with Edge Reversals problem gives you a directed graph. You need to find a path from a source to a destination. However, the graph might not have a direct path. You are allowed to "reverse" any existing edge, but each reversal has a cost of 1. You want to find the path that requires the minimum number of edge reversals.

Why is this asked in interviews?

This is a classic Minimum Cost Path interview question at Meta and Palantir. It tests a candidate's ability to transform a graph problem into a Shortest Path problem. It evaluates if you can think creatively about "edge weights" by assigning a cost of 0 to original edges and a cost of 1 to reversed versions of those edges.

Algorithmic pattern used

The 0-1 BFS or Dijkstra's Algorithm interview pattern is the core here.

1. For every original edge (u, v), add it to a new graph with weight 0.
2. Add a corresponding reversed edge (v, u) with weight 1.
3. Run Dijkstra's or 0-1 BFS (since weights are only 0 and 1) to find the shortest distance from source to destination.
4. The resulting distance is the minimum number of reversals.

Example explanation

Graph: 0 -> 1, 1 -> 2, 2 <- 3. Find path 0 to 3.

1. Path 0 -> 1 -> 2 costs 0.
2. From 2 to 3, there is no original edge, but there is 3 -> 2.
3. We "reverse" 3 -> 2 to get 2 -> 3 with cost 1.
4. Total cost = 0 + 0 + 1 = 1. Only one edge reversal is needed.

Common mistakes candidates make

• Full Graph Search: Trying to use BFS to find all paths and then checking reversals, which is too slow.
• Ignoring the 0-weight edges: Treating all edges (original and reversed) as weight 1, which just finds the shortest path in an undirected graph, not the one with minimum reversals.
• Not using 0-1 BFS: Using Dijkstra when 0-1 BFS would be faster ($O(V+E)$ instead of $O(E \log V)$).

Interview preparation tip

When you encounter a problem where "some moves are free and some have a unit cost," think of 0-1 BFS. It's a powerful optimization of BFS using a deque where 0-cost moves go to the front and 1-cost moves go to the back.