Tejav
#3650

Minimum Cost Path with Edge Reversals

Medium
Graph TheoryHeap (Priority Queue)Shortest PathGraph TraversalPriority Queue
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O((n + e) log n)
Space
O(1)
O(n + e)
💡

Intuition

Time O((n + e) log n)Space O(n + e)

Use Dijkstra's algorithm to find the shortest path while considering both original and reversed edges. This efficiently finds the minimum cost using a priority queue.

⚙️

Algorithm

3 steps
  1. 1Step 1: Construct a graph with both original and reversed edges with adjusted weights.
  2. 2Step 2: Use a priority queue to implement Dijkstra's algorithm from node 0.
  3. 3Step 3: Track the minimum cost to reach each node and return the cost to node n-1.
solution.py20 lines
1import heapq
2
3def minCostPath(n, edges):
4    graph = {}
5    for u, v, w in edges:
6        graph.setdefault(u, []).append((v, w))
7        graph.setdefault(v, []).append((u, 2 * w))
8    pq = [(0, 0)]
9    costs = {i: float('inf') for i in range(n)}
10    costs[0] = 0
11    while pq:
12        cost, node = heapq.heappop(pq)
13        if node == n - 1:
14            return cost
15        for neighbor, weight in graph.get(node, []):
16            new_cost = cost + weight
17            if new_cost < costs[neighbor]:
18                costs[neighbor] = new_cost
19                heapq.heappush(pq, (new_cost, neighbor))
20    return -1
ℹ

Complexity note: Dijkstra's algorithm runs in logarithmic time relative to the number of edges and nodes, making it efficient for sparse graphs.

  • 1Reversing edges can create new paths with different costs.
  • 2Using a priority queue optimizes the search for the shortest path.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.