Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
3.1.
Input
3.2.
Output
3.3.
Explanation
4.
Brute Force Approach
5.
Algorithm
5.1.
C++ Code
5.2.
Java Code
5.3.
Input
5.4.
Output
6.
Complexities
6.1.
Time complexity 
6.2.
Space complexity 
7.
Frequently Asked Questions
7.1.
What do you mean by a simple path in a graph?
7.2.
What distinguishes path cost from root path cost?
7.3.
What is Dynamic programming?
7.4.
How can the longest and shortest path be determined?
7.5.
What is the fastest path-finding algorithm?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Minimum cost path with left, right, bottom, and up moves allowed

Author Manan Singhal
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Dijkstra’s algorithm is one of the essential algorithms that a programmer must be aware of to succeed. The algorithm is straightforward to understand and has a vast horizon of applications. Dijkstra’s Algorithm uses the concepts of Greedy Algorithms. In the article, we will discuss one of its applications: minimum cost paths with left, right, bottom, and up moves allowed.

Minimum cost path

Problem Statement

You have been given a 2-dimensional array. For each corresponding cell, you have given a cost required to cross that particular grid. You need to find the minimum cost to reach from the top left corner to the bottom right corner within the grid.

Multi-dimensional array
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

Input

Input grid

Output

141

Explanation

The minimum cost to reach the bottom right starting from the top left corner will be: 

Case 1: 21+10+13+8+79+6+6+20+20 = 183

Case 2: 21+100+7+12+18+6+6+20+20= 210

Case 3: 21 + 10 + 13 + 8 + 7 + 12 + 18 + 6 + 6 + 20 + 20 = 141

So, we can see that Case 3 will be the minimum cost to reach the bottom right corner and thus our answer is 141.

Brute Force Approach

One of the simplest solutions that comes to our mind while reading this problem is to calculate all the possible costs and store them in an array and find the minimum element from the array. But, when we proceed with the implementation of the above procedure we find that when applying dynamic programming you have a graph with cycles due to the movement in all four directions. So, we can conclude that dynamic programming in this problem or any problem in which an infinite loop can take place is not possible.

Algorithm

With the help of Dijkstra's algorithm, we solve this problem. Each grid cell represents a vertex, with adjacent cells serving as neighboring vertices. We will use the matrix in its current form in Dijkstra's algorithm rather than creating an explicit network from these cells.

The code below also uses the dx and dy arrays, which are intended to streamline the process of visiting a cell's neighboring vertices.

Dijkstra's algorithm

 

Let's start with the implementation of the code.

C++ Code

/* C++ program */
#include <bits/stdc++.h>

using namespace std;

#define ROW 5
#define COL 5

/* class representing row, column indexes, and distance */
struct cell {
	int x, y;
	int distance;
	cell(int x, int y, int distance): x(x), y(y), distance(distance){}
};

/* Cells are inserted after comparison */
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);
}

/* this function returns true if the given cell position is inside the grid else returns false */
bool isCellInsideGrid(int i, int j) {
	return (i >= 0 && i < ROW && j >= 0 && j < COL);
}

/* This function returns the shortest path from the top left corner to the bottom right corner in a 2-dimensional grid */
int shortestPathFromTopLeftToBottomRight(int grid[ROW][COL], int row, int column) {
   
	/* creating a distance variable */
	int dis[row][column];
	/* Initialising the variable to INT_MAX */
	for (int i = 0; i < row; i++) {
    	for (int j = 0; j < column; j++) {
        	dis[i][j] = INT_MAX;
    	}
	}
	
	int dx[] = { -1, 0, 1, 0 };
	int dy[] = { 0, 1, 0, -1 };
	set<cell> st;
	st.insert(cell(0, 0, 0));
	
	/* Initialising top left corner as initial grid position */
	dis[0][0] = grid[0][0];
	while (!st.empty()) {
 		cell k = *st.begin();
 		st.erase(st.begin());
 		for (int i = 0; i < 4; i++) {
  			int x = k.x + dx[i];
  			int y = k.y + dy[i];
  			if (!isCellInsideGrid(x, y)) {
      			continue;
  			}
  			
  			if (dis[x][y] > dis[k.x][k.y] + grid[x][y]) {
   				if (dis[x][y] != INT_MAX) {
       				st.erase(st.find(cell(x, y, dis[x][y])));
   				}
   				/* Inserting cell with new distance */
   				dis[x][y] = dis[k.x][k.y] + grid[x][y];
   				st.insert(cell(x, y, dis[x][y]));
  			}
 		}
	}
	return dis[row - 1][column - 1];
}

/* Main Program */
int main() {
   
	int grid[ROW][COL] = { 21, 100, 7, 12, 18, 10, 13, 8, 79, 6, 100, 13, 81, 84, 6, 88, 94, 41, 100, 20, 9, 32, 11, 100, 20 };
	cout << shortestPathFromTopLeftToBottomRight(grid, ROW, COL) << endl;

	return 0;
}

Java Code

/* Java program */
import java.io.*;
import java.util.*;
class Main {
   static int[] dx = {-1,
       0,
       1,
       0
   };
   static int[] dy = {
       0,
       1,
       0,
       -1
   };
   static int ROW = 5;
   static int COL = 5;
   /* class representing row, column indexes, and distance */
   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;
       }
   }
   /* Cells are inserted using a custom comparator into the 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;
           }
       }
   }
   /* this function returns true if the given cell position is inside the grid else returns false */
   static boolean isCellInsideGrid(int i, int j) {
       return (i >= 0 && i < ROW && j >= 0 && j < COL);
   }
   /* This function returns the shortest path from the top left corner to the bottom right corner in a 2-dimensional grid */
   static int shortestPathFromTopLeftToBottomRight(int[][] grid, int row, int column) {
       /* creating a distance variable */
       int[][] dist = new int[row][column];
       /* Initialising the variable to INT_MAX */
       for (int i = 0; i < row; i++) {
           for (int j = 0; j < column; j++) {
               dist[i][j] = Integer.MAX_VALUE;
           }
       }
       /* Initialising top left corner as initial grid position */
       dist[0][0] = grid[0][0];
       PriorityQueue < Cell > priorityQueue = new PriorityQueue < Cell > (row * column, new distanceComparator());
       priorityQueue.add(new Cell(0, 0, dist[0][0]));
       while (!priorityQueue.isEmpty()) {
           Cell curr = priorityQueue.poll();
           for (int i = 0; i < 4; i++) {
               int rows = curr.x + dx[i];
               int cols = curr.y + dy[i];
               if (isCellInsideGrid(rows, cols)) {
                   if (dist[rows][cols] > dist[curr.x][curr.y] + grid[rows][cols]) {
                       if (dist[rows][cols] != Integer.MAX_VALUE) {
                           Cell adj = new Cell(rows, cols, dist[rows][cols]);
                           priorityQueue.remove(adj);
                       }
                       /* Inserting cell with new distance */
                       dist[rows][cols] = dist[curr.x][curr.y] + grid[rows][cols];
                       priorityQueue.add(new Cell(rows, cols, dist[rows][cols]));
                   }
               }
           }
       }
       return dist[row - 1][column - 1];
   }
   /* Main Program */
   public static void main(String[] args) throws IOException {
       int[][] grid = {
           {
               21,
               100,
               7,
               12,
               18
           },
           {
               10,
               13,
               8,
               79,
               6
           },
           {
               100,
               13,
               81,
               84,
               6
           },
           {
               88,
               94,
               41,
               100,
               20
           },
           {
               9,
               32,
               11,
               100,
               20
           }
       };
       System.out.println(shortestPathFromTopLeftToBottomRight(grid, ROW, COL));
   }
}

Input

Input

Output

141

Complexities

Time complexity 

O(N * N * log N), where N is the grid's number of rows or columns.

Reason: We will traverse the size N array, which contains an array of size N, and applying Dijkstra's algorithm to it will take the time complexity to O(N * log N).

As a result, O(N * N * log N) is the total time complexity.

Space complexity 

O(N * N), where N is the grid's number of rows or columns.

Reason: The complexity of space is of order N * N because we are creating an array of an array with each size N to store the grid.

Check out this problem - Frog Jump

Frequently Asked Questions

What do you mean by a simple path in a graph?

A simple path in geometry is a simple curve, precisely a continuous injective function from an actual number interval to a metric space, topological space, or, more generally. A simple path in graph theory is a path through a graph that doesn't have recurring vertices.

What distinguishes path cost from root path cost?

The speed of the switch interface determines the path cost. The switch port on which the overall cost is lowest to reach the root bridge is known as the root port. The lower path cost path will always be preferred.

What is Dynamic programming?

With the use of a series of simpler subproblems, each of which is solved just once and then stored using the technique known as Dynamic Programming, which can be considered to solve such problems.

How can the longest and shortest path be determined?

The shortest path in a graph formed from G by changing each weight to its opposite is the same as the longest path between two given vertices, s, and t, in a weighted graph G. Since shortest pathways may be discovered in G, it follows the longest paths as well.

What is the fastest path-finding algorithm?

Dijkstra's algorithm is considered to be our fastest path algorithm because it can find the shortest path between two vertices in the graph. The coordinates on the arena are known to be the vertices in the graph.

Conclusion

In the article, we have discussed one popular question: Minimum cost path with left, right, bottom, and up moves allowed. We hope that this article will help you understand the concept of the shortest path, and if you want to learn more about it, check out our other blogs on this topic:

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Minimum Edges to Reverse to Make the Path from a Source to a Destination
Next article
Shortest distance from a guard in a bank
Live masterclass