最短路径(给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步,用分支限界法解决此问题,并给出一个输入数字就可以得到最终结果的Java代码
时间: 2024-01-21 19:15:56 浏览: 49
以下是使用分支限界法解决最短路径问题的Java代码:
```java
import java.util.*;
public class ShortestPath {
static int[][] grid;
static int m, n;
static class Node implements Comparable<Node>{
int row, col, dist;
Node(int row, int col, int dist){
this.row = row;
this.col = col;
this.dist = dist;
}
public int compareTo(Node other){
return Integer.compare(this.dist, other.dist);
}
}
public static int minPathSum(int[][] grid) {
ShortestPath.grid = grid;
m = grid.length;
n = grid[0].length;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(0, 0, grid[0][0]));
while(!pq.isEmpty()){
Node curr = pq.poll();
int row = curr.row;
int col = curr.col;
int dist = curr.dist;
if(row == m-1 && col == n-1){
return dist;
}
if(row+1 < m){
pq.offer(new Node(row+1, col, dist+grid[row+1][col]));
}
if(col+1 < n){
pq.offer(new Node(row, col+1, dist+grid[row][col+1]));
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("请输入矩阵的行数:");
int m = sc.nextInt();
System.out.print("请输入矩阵的列数:");
int n = sc.nextInt();
int[][] grid = new int[m][n];
System.out.println("请输入矩阵的元素:");
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
grid[i][j] = sc.nextInt();
}
}
System.out.println("最小路径和为:" + minPathSum(grid));
}
}
```
输入格式为:
```
请输入矩阵的行数:3
请输入矩阵的列数:3
请输入矩阵的元素:
1 3 1
1 5 1
4 2 1
```
输出结果为:
```
最小路径和为:7
```