Do you think IIT Guwahati certified course can help you in your career?
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.
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.
Example
Input
Output
141
Explanation
The minimum cost to reach the bottom right starting from the top left corner will be:
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.
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;
}
You can also try this code with Online C++ Compiler
/* 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));
}
}
You can also try this code with Online Java Compiler
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.
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:
34+ registered 
