允许向左/向右/向下和向上移动的最小成本路径 _最小成本路径

本文概述

C ++
Java

给定一个二维网格, 该网格的每个像元都包含整数成本, 代表通过该像元所要经过的成本, 我们需要找到一条从左上角像元到右下角像元的路径, 从而使总成本最小。
注意：
假设输入矩阵中不存在负成本周期。
这个问题是下面的问题的延伸。
最小成本路径, 允许左右移动。
在前面的问题中, 只允许向右和向下移动, 但在此问题中, 我们被允许向下, 向上, 向右和向左移动, 即沿所有四个方向移动。
例子：

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.

推荐：请在"实践首先, 在继续解决方案之前。
使用类似于先前问题的动态编程无法解决此问题, 因为此处的当前状态不仅取决于右侧和底部单元, 还取决于左侧和上部单元。我们使用以下方法解决此问题：dijkstra的算法。网格的每个像元代表一个顶点, 相邻像元代表相邻的顶点。我们不会从这些单元格中生成一个明确的图形, 而是将使用dijkstra算法中的矩阵。
在下面的代码中
Dijkstra算法的实现
用来。更改以下实现的代码以应对矩阵表示的隐式图。还请参见下面的代码中dx和dy数组的使用, 这些数组用于简化访问每个像元的相邻顶点的过程。
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 < COL & & j> = 0 & & j < ROW); }//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

【允许向左/向右/向下和向上移动的最小成本路径】输出如下：