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

2021年4月15日15:26:46 发表评论 738 次浏览

## 本文概述

``````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算法的实现

## 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]);

}

//Insert cell with updated distance
dist[rows][cols] = dist[curr.x][curr.y] +
grid[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``````

``327``