Data Modelling & AI Data Structure & Algorithm

Minimum Cost Path with Left, Right, Bottom and Up moves allowed

21 June 2025

0

Given a two-dimensional grid, each cell of which contains an integer cost which represents a cost to traverse through that cell, we need to find a path from the top left cell to the bottom right cell by which the total cost incurred is minimum.

Note: It is assumed that negative cost cycles do not exist in input matrix.

This problem is an extension of problem: Min Cost Path with right and bottom moves allowed.

In the previous problem only going right and the bottom was allowed but in this problem, we are allowed to go bottom, up, right and left i.e. in all 4 directions.

Examples:

A cost grid is given in below diagram, minimum 
cost to reach bottom right from top left 
is 327 (= 31 + 10 + 13 + 47 + 65 + 12 + 18 + 
6 + 33 + 11 + 20 + 41 + 20)

The chosen least cost path is shown in green.

It is not possible to solve this problem using dynamic programming similar to the previous problem because here current state depends not only on the right and bottom cells but also on the left and upper cells. We solve this problem using dijkstra’s algorithm. Each cell of the grid represents a vertex and neighbor cells adjacent vertices. We do not make an explicit graph from these cells instead we will use the matrix as it is in our Dijkstra’s algorithm.

In the below code, Dijkstra’s algorithm’s implementation is used. The code implemented below is changed to cope with matrix represented implicit graph. Please also see use of dx and dy arrays in the below code, these arrays are taken for simplifying the process of visiting neighbor vertices of each cell.

Below is the implementation of the above approach:

C++

// C++ program to get least cost path in a grid from
// top-left to bottom-right
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ROW 5
#define COL 5
 
// structure for information of each cell
struct cell {
    int x, y;
    int distance;
    cell(int x, int y, int distance)
        : x(x)
        , y(y)
        , distance(distance)
    {
    }
};
 
// Utility method for comparing two cells
bool operator<(const cell& a, const cell& b)
{
    if (a.distance == b.distance) {
        if (a.x != b.x)
            return (a.x < b.x);
        else
            return (a.y < b.y);
    }
    return (a.distance < b.distance);
}
 
// Utility method to check whether a point is
// inside the grid or not
bool isInsideGrid(int i, int j)
{
    return (i >= 0 && i < ROW && j >= 0 && j < COL);
}
 
// Method returns minimum cost to reach bottom
// right from top left
int shortest(int grid[ROW][COL], int row, int col)
{
    int dis[row][col];
 
    // initializing distance array by INT_MAX
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            dis[i][j] = INT_MAX;
 
    // direction arrays for simplification of getting
    // neighbour
    int dx[] = { -1, 0, 1, 0 };
    int dy[] = { 0, 1, 0, -1 };
 
    set<cell> st;
 
    // insert (0, 0) cell with 0 distance
    st.insert(cell(0, 0, 0));
 
    // initialize distance of (0, 0) with its grid value
    dis[0][0] = grid[0][0];
 
    // loop for standard dijkstra's algorithm
    while (!st.empty()) {
        // get the cell with minimum distance and delete
        // it from the set
        cell k = *st.begin();
        st.erase(st.begin());
 
        // looping through all neighbours
        for (int i = 0; i < 4; i++) {
            int x = k.x + dx[i];
            int y = k.y + dy[i];
 
            // if not inside boundary, ignore them
            if (!isInsideGrid(x, y))
                continue;
 
            // If distance from current cell is smaller,
            // then update distance of neighbour cell
            if (dis[x][y] > dis[k.x][k.y] + grid[x][y]) {
                // If cell is already there in set, then
                // remove its previous entry
                if (dis[x][y] != INT_MAX)
                    st.erase(
                        st.find(cell(x, y, dis[x][y])));
 
                // update the distance and insert new
                // updated cell in set
                dis[x][y] = dis[k.x][k.y] + grid[x][y];
                st.insert(cell(x, y, dis[x][y]));
            }
        }
    }
 
    // uncomment below code to print distance
    // of each cell from (0, 0)
    /*
    for (int i = 0; i < row; i++, cout << endl)
        for (int j = 0; j < col; j++)
            cout << dis[i][j] << " ";
    */
    // dis[row - 1][col - 1] will represent final
    // distance of bottom right cell from top left cell
    return dis[row - 1][col - 1];
}
 
// Driver code to test above methods
int main()
{
    int grid[ROW][COL]
        = { 31, 100, 65,  12,  18,  10, 13, 47,  157,
            6,  100, 113, 174, 11,  33, 88, 124, 41,
            20, 140, 99,  32,  111, 41, 20 };
 
    cout << shortest(grid, ROW, COL) << endl;
    return 0;
}

Java

// Java program to get least cost path 
// in a grid from top-left to bottom-right
import java.io.*;
import java.util.*;
 
class GFG{
     
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };
static int ROW = 5;
static int COL = 5;
 
// Custom class for representing
// row-index, column-index &
// distance of each cell
static class Cell
{
    int x;
    int y;
    int distance;
     
    Cell(int x, int y, int distance) 
    {
        this.x = x;
        this.y = y;
        this.distance = distance;
    }
}
 
// Custom comparator for inserting cells 
// into Priority Queue
static class distanceComparator 
  implements Comparator<Cell>
{
    public int compare(Cell a, Cell b)
    {
        if (a.distance < b.distance)
        {
            return -1;
        }
        else if (a.distance > b.distance)
        {
            return 1;
        }
        else {return 0;}
    }
}
 
// Utility method to check whether current
// cell is inside grid or not
static boolean isInsideGrid(int i, int j)
{
    return (i >= 0 && i < ROW &&
            j >= 0 && j < COL);
}
 
// Method to return shortest path from 
// top-corner to bottom-corner in 2D grid
static int shortestPath(int[][] grid, int row, 
                                      int col)
{
    int[][] dist = new int[row][col];
     
    // Initializing distance array by INT_MAX 
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            dist[i][j] = Integer.MAX_VALUE;
        }
    }
     
    // Initialized source distance as
    // initial grid position value
    dist[0][0] = grid[0][0];
     
    PriorityQueue<Cell> pq = new PriorityQueue<Cell>(
                  row * col, new distanceComparator());
                   
    // Insert source cell to priority queue
    pq.add(new Cell(0, 0, dist[0][0]));
    while (!pq.isEmpty())
    {
        Cell curr = pq.poll();
        for(int i = 0; i < 4; i++)
        {
            int rows = curr.x + dx[i];
            int cols = curr.y + dy[i];
             
            if (isInsideGrid(rows, cols))
            {
                if (dist[rows][cols] > 
                    dist[curr.x][curr.y] + 
                    grid[rows][cols])
                {
                     
                    // If Cell is already been reached once,
                    // remove it from priority queue
                    if (dist[rows][cols] != Integer.MAX_VALUE)
                    {
                        Cell adj = new Cell(rows, cols, 
                                       dist[rows][cols]);
                                        
                        pq.remove(adj);
                    }
                     
                    // Insert cell with updated distance 
                    dist[rows][cols] = dist[curr.x][curr.y] +
                                       grid[rows][cols];
                                        
                    pq.add(new Cell(rows, cols, 
                               dist[rows][cols]));
                }
            }
        }
    }
    return dist[row - 1][col - 1];
}
 
// Driver code
public static void main(String[] args) 
throws IOException
{
    int[][] grid = { { 31, 100, 65, 12, 18 },
                     { 10, 13, 47, 157, 6 },
                     { 100, 113, 174, 11, 33 },
                     { 88, 124, 41, 20, 140 },
                     { 99, 32, 111, 41, 20 } };
                      
    System.out.println(shortestPath(grid, ROW, COL));
}
}
 
// This code is contributed by jigyansu

Python3

# Python program to get least cost path in a grid from
# top-left to bottom-right
from functools import cmp_to_key
 
ROW = 5
COL = 5
 
def mycmp(a,b):
     
    if (a.distance == b.distance):
        if (a.x != b.x):
            return (a.x - b.x)
        else:
            return (a.y - b.y)
    return (a.distance - b.distance)
 
# structure for information of each cell
class cell:
 
    def __init__(self,x, y, distance):
        self.x = x
        self.y = y
        self.distance = distance
 
# Utility method to check whether a point is
# inside the grid or not
def isInsideGrid(i, j):
    return (i >= 0 and i < ROW and j >= 0 and j < COL)
 
# Method returns minimum cost to reach bottom
# right from top left
def shortest(grid, row, col):
    dis = [[0 for i in range(col)]for j in range(row)]
 
    # initializing distance array by INT_MAX
    for i in range(row):
        for j in range(col):
            dis[i][j] = 1000000000
 
    # direction arrays for simplification of getting
    # neighbour
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
 
    st = []
 
    # insert (0, 0) cell with 0 distance
    st.append(cell(0, 0, 0))
 
    # initialize distance of (0, 0) with its grid value
    dis[0][0] = grid[0][0]
 
    # loop for standard dijkstra's algorithm
    while (len(st)!=0):
 
        # get the cell with minimum distance and delete
        # it from the set
        k = st[0]
        st = st[1:]
 
        # looping through all neighbours
        for i in range(4):
 
            x = k.x + dx[i]
            y = k.y + dy[i]
 
            # if not inside boundary, ignore them
            if (isInsideGrid(x, y) == 0):
                continue
 
            # If distance from current cell is smaller, then
            # update distance of neighbour cell
            if (dis[x][y] > dis[k.x][k.y] + grid[x][y]):
                # update the distance and insert new updated
                # cell in set
                dis[x][y] = dis[k.x][k.y] + grid[x][y]
                st.append(cell(x, y, dis[x][y]))
 
        st.sort(key=cmp_to_key(mycmp))
 
    # uncomment below code to print distance
    # of each cell from (0, 0)
 
    # for i in range(row):
    #     for j in range(col):
    #         print(dis[i][j] ,end= " ")
    #     print()
 
    # dis[row - 1][col - 1] will represent final
    # distance of bottom right cell from top left cell
    return dis[row - 1][col - 1]
 
# Driver code to test above methods
 
grid = [[31, 100, 65, 12, 18], [10, 13, 47, 157, 6], [100, 113, 174, 11, 33], [88, 124, 41, 20, 140],[99, 32, 111, 41, 20]]
print(shortest(grid, ROW, COL))
 
# This code is contributed by shinjanpatra

C#

using System;
using System.Collections.Generic;
 
class GFG {
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static int ROW = 5;
    static int COL = 5;
 
    // Custom class for representing
    // row-index, column-index &
    // distance of each cell
    class Cell {
        public int x;
        public int y;
        public int distance;
 
        public Cell(int x, int y, int distance)
        {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }
 
    // Custom comparator for sorting cells
    // in ascending order of distance
    class DistanceComparer : IComparer<Cell> {
        public int Compare(Cell a, Cell b)
        {
            if (a.distance < b.distance) {
                return -1;
            }
            else if (a.distance > b.distance) {
                return 1;
            }
            else {
                return 0;
            }
        }
    }
 
    // Utility method to check whether current
    // cell is inside grid or not
    static bool IsInsideGrid(int i, int j)
    {
        return (i >= 0 && i < ROW && j >= 0 && j < COL);
    }
 
    // Method to return shortest path from
    // top-corner to bottom-corner in 2D grid
    static int ShortestPath(int[][] grid, int row, int col)
    {
        int[][] dist = new int[row][];
        for (int i = 0; i < row; i++) {
            dist[i] = new int[col];
            for (int j = 0; j < col; j++) {
                dist[i][j] = int.MaxValue;
            }
        }
 
        // Initialized source distance as
        // initial grid position value
        dist[0][0] = grid[0][0];
 
        List<Cell> pq = new List<Cell>();
        pq.Add(new Cell(0, 0, dist[0][0]));
        pq.Sort(new DistanceComparer());
 
        while (pq.Count > 0) {
            Cell curr = pq[0];
            pq.RemoveAt(0);
 
            for (int i = 0; i < 4; i++) {
                int rows = curr.x + dx[i];
                int cols = curr.y + dy[i];
 
                if (IsInsideGrid(rows, cols)) {
                    if (dist[rows][cols]
                        > dist[curr.x][curr.y]
                              + grid[rows][cols]) {
                        // If Cell is already been reached
                        // once, remove it from list
                        if (dist[rows][cols]
                            != int.MaxValue) {
                            Cell adj = new Cell(
                                rows, cols,
                                dist[rows][cols]);
                            pq.Remove(adj);
                        }
 
                        // Insert cell with updated distance
                        dist[rows][cols]
                            = dist[curr.x][curr.y]
                              + grid[rows][cols];
                        pq.Add(new Cell(rows, cols,
                                        dist[rows][cols]));
                        pq.Sort(new DistanceComparer());
                    }
                }
            }
        }
 
        return dist[row - 1][col - 1];
    }
 
    // Driver code
    static void Main(string[] args)
    {
        int[][] grid
            = { new int[] { 31, 100, 65, 12, 18 },
                new int[] { 10, 13, 47, 157, 6 },
                new int[] { 100, 113, 174, 11, 33 },
                new int[] { 88, 124, 41, 20, 140 },
                new int[] { 99, 32, 111, 41, 20 } };
 
        Console.WriteLine(ShortestPath(grid, ROW, COL));
    }
}
 
// This code is contributed by phasing17

Javascript

<script>
  
// Javascript program to get least cost path in a grid from
// top-left to bottom-right
var ROW = 5
var COL = 5
 
// structure for information of each cell
class cell
{
    constructor(x, y, distance)
    {
        this.x = x;
        this.y = y;
        this.distance = distance;
    }
};
 
 
// Utility method to check whether a point is
// inside the grid or not
function isInsideGrid(i, j)
{
    return (i >= 0 && i < ROW && j >= 0 && j < COL);
}
 
// Method returns minimum cost to reach bottom
// right from top left
function shortest(grid, row, col)
{
    var dis = Array.from(Array(row), ()=>Array(col).fill(0));
 
    // initializing distance array by INT_MAX
    for (var i = 0; i < row; i++)
        for (var j = 0; j < col; j++)
            dis[i][j] = 1000000000;
 
    // direction arrays for simplification of getting
    // neighbour
    var dx = [-1, 0, 1, 0];
    var dy = [0, 1, 0, -1];
 
    var st = [];
 
    // insert (0, 0) cell with 0 distance
    st.push(new cell(0, 0, 0));
 
    // initialize distance of (0, 0) with its grid value
    dis[0][0] = grid[0][0];
 
    // loop for standard dijkstra's algorithm
    while (st.length!=0)
    {
        // get the cell with minimum distance and delete
        // it from the set
        var k = st[0];
        st.shift();
 
        // looping through all neighbours
        for (var i = 0; i < 4; i++)
        {
            var x = k.x + dx[i];
            var y = k.y + dy[i];
 
            // if not inside boundary, ignore them
            if (!isInsideGrid(x, y))
                continue;
 
            // If distance from current cell is smaller, then
            // update distance of neighbour cell
            if (dis[x][y] > dis[k.x][k.y] + grid[x][y])
            {
                // update the distance and insert new updated
                // cell in set
                dis[x][y] = dis[k.x][k.y] + grid[x][y];
                st.push(new cell(x, y, dis[x][y]));
            }
        }
        st.sort((a,b)=>{
            if (a.distance == b.distance)
    {
        if (a.x != b.x)
            return (a.x - b.x);
        else
            return (a.y - b.y);
    }
    return (a.distance - b.distance);
        });
    }
 
    // uncomment below code to print distance
    // of each cell from (0, 0)
    /*
    for (int i = 0; i < row; i++, cout << endl)
        for (int j = 0; j < col; j++)
            cout << dis[i][j] << " ";
    */
    // dis[row - 1][col - 1] will represent final
    // distance of bottom right cell from top left cell
    return dis[row - 1][col - 1];
}
 
// Driver code to test above methods
var grid =
[
    [31, 100, 65, 12, 18],
    [10, 13, 47, 157, 6],
    [100, 113, 174, 11, 33],
    [88, 124, 41, 20, 140],
    [99, 32, 111, 41, 20]
];
document.write(shortest(grid, ROW, COL));
 
// This code is contributed by rutvik_56.
 
</script>

Output

Time Complexity: O(N²log N), The Dijkstra’s algorithm used in the program has a time complexity of O(E log V) where E is the number of edges and V is the number of vertices. In this program, for each cell, we check its four neighbors, so the number of edges E in the worst case would be 4 times the number of cells (N^2) in the grid. Therefore, the time complexity of the program is O(4N^2logN^2), which simplifies to O(N^2 logN).
Auxiliary Space: O(N²), In this program, we are using a 2D array to store the distances from the top-left cell to each cell in the grid. The size of this array is N^2. We are also using a set to store the cells with their distances. In the worst case, all cells in the grid could be present in the set, so the size of the set could also be N^2. Therefore, the space complexity of the program is O(N^2).

This article is contributed by Utkarsh Trivedi. If you like neveropen and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Minimum Cost Path with Left, Right, Bottom and Up moves allowed

C++

Java

Python3

C#

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

The Boox Palma 2 Pro is a brilliant but unnecessarily complex e-reader

The Pixel Watch 4’s quiet upgrade that actually matters

Google Photos inches closer to bringing back this photo editing tool

5 surprising ways I use Google Maps that have nothing to do with navigation

EDITOR PICKS

The Boox Palma 2 Pro is a brilliant but unnecessarily complex e-reader

The Pixel Watch 4’s quiet upgrade that actually matters

Google Photos inches closer to bringing back this photo editing tool

POPULAR POSTS

The Boox Palma 2 Pro is a brilliant but unnecessarily complex e-reader

The Pixel Watch 4’s quiet upgrade that actually matters

Google Photos inches closer to bringing back this photo editing tool

POPULAR CATEGORY

ABOUT US

FOLLOW US