Minimum Cost Path with Edge Reversals

medium graph theory dijkstra shortest path

Problem

You have a directed weighted graph with n nodes. Each edge [u, v, w] goes from u to v with cost w. When you arrive at a node, you may reverse one of its incoming edges once: an original edge v → u can be traversed as u → v, but a reversed traversal costs 2·w. Return the minimum total cost from node 0 to node n − 1, or −1 if unreachable.

Key insight: reversing edge [u, v, w] is equivalent to having an extra edge v → u with cost 2·w always available. Add those reverse edges, then run Dijkstra.

Inputn = 4, edges = [[0,1,3],[3,1,1],[2,3,4],[0,2,2]]

Output5

Take 0 → 1 (cost 3), then reverse 3 → 1 into 1 → 3 at cost 2·1 = 2. Total = 5.

n (number of nodes)

edges (u,v,w ; semicolon-separated)

import heapq

def minCost(n, edges):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))        # original edge u -> v
        adj[v].append((u, 2 * w))    # reversed edge v -> u costs 2w
    dist = [float('inf')] * n
    dist[0] = 0
    pq = [(0, 0)]                     # (cost, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:              # stale entry, skip
            continue
        if u == n - 1:
            return d
        for v, w in adj[u]:          # relax neighbours
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return -1

function minCost(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) {
    adj[u].push([v, w]);          // original edge u -> v
    adj[v].push([u, 2 * w]);      // reversed edge v -> u costs 2w
  }
  const dist = new Array(n).fill(Infinity);
  dist[0] = 0;
  const pq = [[0, 0]];            // [cost, node] min-heap
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift();
    if (d > dist[u]) continue;    // stale entry, skip
    if (u === n - 1) return d;
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        pq.push([dist[v], v]);
      }
    }
  }
  return -1;
}

int minCost(int n, int[][] edges) {
    List<int[]>[] adj = new List[n];
    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    for (int[] e : edges) {
        adj[e[0]].add(new int[]{e[1], e[2]});       // u -> v
        adj[e[1]].add(new int[]{e[0], 2 * e[2]});   // v -> u costs 2w
    }
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[0] = 0;
    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    pq.add(new long[]{0, 0});
    while (!pq.isEmpty()) {
        long[] top = pq.poll();
        long d = top[0]; int u = (int) top[1];
        if (d > dist[u]) continue;                  // stale entry
        if (u == n - 1) return (int) d;
        for (int[] nb : adj[u]) {
            if (d + nb[1] < dist[nb[0]]) {
                dist[nb[0]] = d + nb[1];
                pq.add(new long[]{dist[nb[0]], nb[0]});
            }
        }
    }
    return -1;
}

int minCost(int n, vector<vector<int>>& edges) {
    vector<vector<pair<int,int>>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back({e[1], e[2]});          // u -> v
        adj[e[1]].push_back({e[0], 2 * e[2]});      // v -> u costs 2w
    }
    vector<long long> dist(n, LLONG_MAX);
    dist[0] = 0;
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;                  // stale entry
        if (u == n - 1) return (int) d;
        for (auto& [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    return -1;
}

Explanation

The trick is to turn the "reverse an edge" rule into plain extra edges, after which the whole thing becomes an ordinary shortest-path problem solvable with Dijkstra.

For every original edge u → v with cost w, the rule says: standing at v, you may reverse this incoming edge and walk v → u, paying 2·w. Since the switch at each node may be used any number of times across different edges (each edge's reversal is decided independently and is "valid for that single move"), we can simply pre-add a directed edge v → u of cost 2·w to the graph. No edge is ever harmed by having this option available — Dijkstra will only use it when it is cheaper.

So we build an adjacency list that contains both the original edges and their reversed twins, then run a standard Dijkstra from node 0. We keep a dist array and a min-heap of (cost, node). Each time we pop the cheapest unsettled node, we relax all of its outgoing edges (original and reversed alike).

All weights are non-negative (w and 2·w are both positive), which is exactly the condition Dijkstra needs. The first time we pop node n − 1 we have its final answer; if the heap empties without reaching it, the target is unreachable and we return −1.

Example: with edges = [[0,1,3],[3,1,1],[2,3,4],[0,2,2]] we add reverse edges such as 1 → 3 at cost 2·1 = 2. Dijkstra finds 0 → 1 (3) then the reversed 1 → 3 (2), for a total of 5.

Time: O((V + E) log V) Space: O(V + E)