Skip to main content
Talentd

Minimum Cost Path with Edge Reversals - Solution & Explanation

MediumGraphHeap (Priority Queue)Shortest Path14 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

Problem Statement

You are given a directed, weighted graph with n nodes labeled from 0 to n - 1, and an array edges where edges[i] = [ui, vi, wi] represents a directed edge from node ui to node vi with cost wi.

Each node ui has a switch that can be used at most once: when you arrive at ui and have not yet used its switch, you may activate it on one of its incoming edges vi → ui reverse that edge to ui → vi and immediately traverse it.

The reversal is only valid for that single move, and using a reversed edge costs 2 * wi.

Return the minimum total cost to travel from node 0 to node n - 1. If it is not possible, return -1.

 

Example 1:

Input: n = 4, edges = [[0,1,3],[3,1,1],[2,3,4],[0,2,2]]

Output: 5

Explanation:

  • Use the path 0 → 1 (cost 3).
  • At node 1 reverse the original edge 3 → 1 into 1 → 3 and traverse it at cost 2 * 1 = 2.
  • Total cost is 3 + 2 = 5.

Example 2:

Input: n = 4, edges = [[0,2,1],[2,1,1],[1,3,1],[2,3,3]]

Output: 3

Explanation:

  • No reversal is needed. Take the path 0 → 2 (cost 1), then 2 → 1 (cost 1), then 1 → 3 (cost 1).
  • Total cost is 1 + 1 + 1 = 3.

 

Constraints:

  • 2 <= n <= 5 * 104
  • 1 <= edges.length <= 105
  • edges[i] = [ui, vi, wi]
  • 0 <= ui, vi <= n - 1
  • 1 <= wi <= 1000

Approach Overview

Problem Overview: You are given a directed graph and want the cheapest way to travel from a source node to a destination. Moving along an existing edge costs 0, but reversing an edge direction costs 1. The task is to compute the minimum total cost required to reach the target node.

Approach 1: DFS/Brute Force Exploration (Exponential Time, O(V) space)

A straightforward idea is to explore all possible paths from the source. For each node, traverse both the original outgoing edges (cost 0) and any incoming edges treated as reversed edges (cost 1). Track the accumulated cost and keep the minimum seen when reaching the destination. This approach effectively searches the entire state space of paths. Because graphs may contain cycles and multiple branching choices, the time complexity becomes exponential in the worst case. It mainly helps reason about the problem but is impractical for large graphs.

Approach 2: 0-1 BFS with Deque (O(V + E) time, O(V + E) space)

The key observation is that every edge weight is either 0 or 1. Build an augmented graph where the original edge u → v has weight 0, and the reverse edge v → u has weight 1. Instead of a priority queue, use a deque. When relaxing an edge with cost 0, push the node to the front; when the cost is 1, push it to the back. This keeps nodes ordered by shortest distance without a heap. The algorithm behaves like BFS but respects edge weights, producing optimal shortest paths efficiently. This method is common in graph problems where weights are limited to two values.

Approach 3: Dijkstra's Algorithm with Min Heap (O((V + E) log V) time, O(V + E) space)

Treat the problem as a standard shortest path computation. Construct an adjacency list where each original edge has weight 0 and its reversed counterpart has weight 1. Run Dijkstra's algorithm starting from the source node using a priority queue. Each time you pop the smallest distance node, relax its neighbors and update distances if a cheaper path is found. The heap guarantees the next processed node always has the minimum current cost. This approach works for any non‑negative weights and fits naturally into the shortest path family of problems.

Recommended for interviews: Interviewers typically expect the shortest path formulation. Showing the graph transformation (adding reversed edges with cost 1) demonstrates strong modeling skills. Implementing Dijkstra with a priority queue is the safest general solution, while mentioning the 0-1 BFS optimization shows deeper understanding of graph edge-weight constraints.

Solution

According to the problem description, we can construct a directed graph g where each edge (u, v) allows for two types of traversal:

  • Direct traversal with cost w, corresponding to edge (u, v).
  • Reverse traversal with cost 2w, corresponding to edge (v, u).

Then, we can use Dijkstra's algorithm on graph g to find the shortest path from node 0 to node n-1, which corresponds to the minimum total cost required.

Specifically, we define a priority queue pq, where each element is a tuple (d, u), indicating that the current minimum cost to reach node u is d. We also define an array dist, where dist[u] represents the minimum cost from node 0 to node u. Initially, we set dist[0] = 0, and the costs for all other nodes to infinity, then push (0, 0) into the queue.

In each iteration, we extract the node (d, u) with the minimum cost from the priority queue. If d is greater than dist[u], we skip this node. Otherwise, we traverse all neighbors v of node u, calculating the new cost nd = d + w to reach node v via node u. If nd is less than dist[v], we update dist[v] = nd and push (nd, v) into the queue.

When we extract node n-1, the current d is the minimum total cost from node 0 to node n-1. If the priority queue becomes empty and node n-1 has not been extracted, it implies that node n-1 is unreachable, so we return -1.

The time complexity is O(n + m times log m), and the space complexity is O(n + m). Here, n and m refer to the number of nodes and edges, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS / Brute Force Path SearchExponentialO(V)Conceptual understanding or very small graphs
0-1 BFS using DequeO(V + E)O(V + E)Best when edge weights are only 0 or 1
Dijkstra's Algorithm with Min HeapO((V + E) log V)O(V + E)General shortest path solution using priority queue

Video Solution

Minimum Cost Path with Edge Reversals | Easiest Explanation | Leetcode 3650 | codestorywithMIK • codestorywithMIK • 10,077 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Cost Path with Edge Reversals easy or hard?
The problem is generally classified as Medium difficulty. The main challenge is recognizing that reversing an edge can be treated as a weighted edge in a shortest path graph. Once modeled correctly, standard algorithms like Dijkstra or 0-1 BFS solve it efficiently.
Minimum Cost Path with Edge Reversals Python/Java solution
The standard implementation constructs an adjacency list with edges weighted 0 for original direction and 1 for reversed direction. Dijkstra's algorithm with a min heap computes the minimum distance array. The same logic works across Python, Java, C++, Go, and TypeScript with language-specific priority queue implementations.
How to solve Minimum Cost Path with Edge Reversals in O(n)?
Transform the graph by adding reversed edges with weight 1 while keeping original edges with weight 0. Then run 0-1 BFS using a deque. Push nodes to the front for weight 0 edges and to the back for weight 1 edges, producing a shortest path in O(V + E) time.
What is the best approach for Minimum Cost Path with Edge Reversals?
The most practical solution models the graph so that every original edge has cost 0 and the reversed edge has cost 1. Running Dijkstra's algorithm with a priority queue then finds the minimum cost path. When edge weights are strictly 0 or 1, an optimized 0-1 BFS approach achieves O(V + E) time.
Is Minimum Cost Path with Edge Reversals asked at Google/Amazon/Meta?
Variations of this problem appear in interviews at companies that emphasize graph algorithms, including Google and Amazon. The core idea—transforming edge costs and applying Dijkstra or 0-1 BFS—is a common pattern for shortest path interview questions.
What data structure is used in Minimum Cost Path with Edge Reversals?
The main data structure is a priority queue (min heap) when implementing Dijkstra's algorithm. For the optimized version, a deque is used to implement 0-1 BFS. Both rely on adjacency lists to represent the graph efficiently.
What is the time complexity of Minimum Cost Path with Edge Reversals?
Using Dijkstra's algorithm with a binary heap takes O((V + E) log V) time and O(V + E) space, where V is the number of vertices and E is the number of edges. If implemented with 0-1 BFS due to weights being only 0 and 1, the complexity improves to O(V + E).

Ready to solve this problem?

Practice Minimum Cost Path with Edge Reversals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Cost to Reach Destination in Time