Minimum Cost Path with Teleportations

The Problem

In this post, we tackle a complex shortest-path problem on a grid. Unlike standard grid DP problems where you only move right or down, this challenge introduces arbitrary movement and “wormholes.”

The goal is to reach $(m-1, n-1)$ from $(0, 0)$ with the lowest cost.

Movement Rules

1. Adjacent Moves: Move Up, Down, Left, or Right. Cost = grid[new_row][new_col].
2. Teleportation: Use a jump from $(r1, c1)$ to $(r2, c2)$ with a fixed cost. You can use at most $k$ teleports.

Visualizing the Optimal Path

Below is a visualization of the grid [[1,3,3],[2,5,4],[4,3,5]] with $k=1$. The path highlights how skipping expensive cells via teleportation can optimize the total cost.

The Multi-Universe Algorithm

To solve this problem efficiently, we break the logic into three distinct phases. The core idea is to treat the number of available teleportations as a “universe” index. Moving from universe $k$ to $k+1$ represents the act of using one teleportation jump.

1. Initial DP Calculation: We compute the minimum cost path from every cell to the target $(m-1, n-1)$ assuming no teleportations are used.
2. Universe Transition: We update the costs by projecting the possible jumps from Universe $k$ to Universe $k+1$.
3. Local Relaxation: After a teleportation jump, we re-run a relaxation (or a simplified DP) to ensure that the new, potentially lower costs are propagated to neighboring cells in the new universe.

2.1 Simple DP Approach

In the first step, we ignore teleportations entirely. Since we want the cost from any cell $(i, j)$ to the target $(m-1, n-1)$, we use a bottom-up DP starting from the destination.

In this specific implementation, we define g[i][j] as the cost to reach the target after having arrived at cell $(i, j)$.

// Compute optimal cost grid G[i][j] = min cost from (i,j) to (m-1,n-1)
let mut g = vec![vec![0; n]; m];

// Base case: destination has cost 0 (we are already there)
g[m - 1][n - 1] = 0;

// Fill last row (can only go right)
for j in (0..n - 1).rev() {
    g[m - 1][j] = grid[m - 1][j + 1] + g[m - 1][j + 1];
}

// Fill last column (can only go down)
for i in (0..m - 1).rev() {
    g[i][n - 1] = grid[i + 1][n - 1] + g[i + 1][n - 1];
}

// Fill rest of grid from bottom-right to top-left
for i in (0..m - 1).rev() {
    for j in (0..n - 1).rev() {
        g[i][j] = (grid[i + 1][j] + g[i + 1][j]).min(grid[i][j + 1] + g[i][j + 1]);
    }
}

// If no teleportations allowed, return cost from start (plus start cell cost)
if k == 0 {
    return grid[0][0] + g[0][0];
}

Step 1 Visualization:

The Cost GridHere is the transition from the Input Grid to the DP Cost Matrix ($g$). The cost matrix represents the minimum distance to the target using only standard moves (Right and Down).

The Multi-Universe Algorithm

To solve this problem efficiently, we break the logic into three distinct phases. The core idea is to treat the number of available teleportations as a “universe” index. Moving from universe $k$ to $k+1$ represents the act of using one teleportation jump.

1. Initial DP Calculation: Compute the minimum cost path from every cell to the target $(m-1, n-1)$ assuming no teleportations.
2. Universe Transition: Update the costs by projecting possible jumps from Universe $k$ to Universe $k+1$.
3. Local Relaxation: Re-run a relaxation step to ensure new, lower costs are propagated to neighboring cells in the new universe.

2.1 Simple DP Approach

In the first step, we ignore teleportations. Since we want the cost from any cell $(i, j)$ to the target $(m-1, n-1)$, we use a bottom-up DP starting from the destination. In this implementation, g[i][j] is the cost to reach the target after having arrived at cell $(i, j)$.

// Compute optimal cost grid G[i][j] = min cost from (i,j) to (m-1,n-1)
let mut g = vec![vec![0; n]; m];

// Base case: destination has cost 0
g[m - 1][n - 1] = 0;

// Fill last row (can only go right)
for j in (0..n - 1).rev() {
    g[m - 1][j] = grid[m - 1][j + 1] + g[m - 1][j + 1];
}

// Fill last column (can only go down)
for i in (0..m - 1).rev() {
    g[i][n - 1] = grid[i + 1][n - 1] + g[i + 1][n - 1];
}

// Fill rest of grid from bottom-right to top-left
for i in (0..m - 1).rev() {
    for j in (0..n - 1).rev() {
        g[i][j] = (grid[i + 1][j] + g[i + 1][j]).min(grid[i][j + 1] + g[i][j + 1]);
    }
}

// If no teleportations allowed, return cost from start
if k == 0 {
    return grid[0][0] + g[0][0];
}

Step 1 Visualization:

Initial DP StateThe resulting matrix $g$ represents the “Walking Distance” to the exit. For our example grid = [[1,3,3],[2,5,4],[4,3,5]], the DP table looks like this:

2.2 Universe Transition:

(Teleportation Update)To update from Universe $k$ to $k+1$, we must find the best teleportation target. By sorting cells by Grid Value then by DP Value, we achieve a linear-time update.

fn teleportation_update(grid: &Vec<Vec<i32>>, g: &mut Vec<Vec<i32>>) {
    let m = grid.len();
    let n = grid[0].len();

    let mut cells = Vec::new();
    for i in 0..m {
        for j in 0..n {
            cells.push((grid[i][j], g[i][j], i, j));
        }
    }
    
    // Sort primarily by grid value for valid jumps, 
    // and secondarily by DP value to find the best target.
    cells.sort_by_key(|&(val, g_val, _, _)| (val, g_val));

    let mut min_g_so_far = i32::MAX;
    for (grid_val, g_val, i, j) in cells {
        // Current cell teleports to the best cell encountered so far
        g[i][j] = g[i][j].min(min_g_so_far);
        min_g_so_far = min_g_so_far.min(g[i][j]);
    }
}

Step 2 Visualization:

Universe TransitionAfter the teleportation update, the costs “collapse” as cells discover shortcuts. The matrix $g$ updates from the initial state to the “1-jump” state:

2.3 Local Relaxation

After teleporting, we treat the new values in as updated “exit points.” We then perform a relaxation pass to ensure that the adjacent cells are aware of these new potential paths.

fn relaxation_update(grid: &Vec<Vec<i32>>, g: &mut Vec<Vec<i32>>) {
    let m = grid.len();
    let n = grid[0].len();

    // Relax from bottom-right to top-left
    for i in (0..m).rev() {
        for j in (0..n).rev() {
            if i == m - 1 && j == n - 1 {
                continue; // destination remains the base case 0
            }

            let mut min_cost = g[i][j];

            // Check if walking Down provides a better cost
            if i + 1 < m {
                min_cost = min_cost.min(grid[i + 1][j] + g[i + 1][j]);
            }

            // Check if walking Right provides a better cost
            if j + 1 < n {
                min_cost = min_cost.min(grid[i][j + 1] + g[i][j + 1]);
            }

            g[i][j] = min_cost;
        }
    }
}

Step 3 Visualization: Final Relaxation

This animation shows the values “settling” into their final state for Universe 1. Notice how the teleportation at propagates its value of to the cells above it.

By repeating Step 2 and Step 3 exactly times, we effectively explore all possible paths that use up to teleportations. The final answer will be found at grid[0][0] + g[0][0].

To wrap up your Distill post, here is the final content including the Complexity Analysis, a Conclusion, and a Manim script you can use to generate a professional-grade animation for your blog.

3. Complexity Analysis

The efficiency of this “Multi-Universe” approach lies in how it avoids the overhead of a full graph search by leveraging the grid’s structure and sorting.

• Time Complexity:
• Initial DP: to fill the grid once.
• Universe Transitions: For each of the teleportations, we perform a sort taking and a linear sweep of .
• Relaxation: Each relaxation pass takes .

• Total: . Given is usually small, this is significantly faster than a general Dijkstra on a dense graph of teleports.

• Space Complexity: if we overwrite the grid in each universe, or if we choose to store every state for visualization.

4. Algorithm Visualization ()

5. Conclusion

This problem was an incredible exercise in 3D Dynamic Programming and state-space reduction. While the problem initially presents as a shortest-path challenge on a graph, viewing it through the lens of “Universe Transitions” allows us to optimize the teleportation logic using a simple sorting trick.

By separating the walking logic (DP) from the jumping logic (Sorting/Sweep), we turned a potentially exponential search into a clean, iterative process. It’s a perfect example of how re-indexing our state can simplify complex interactions.