Java 解决最短路径问题

WechatIMG59.jpeg

最短路径问题

wiki:最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。

图解

矩阵最小路径问题-左上右下(1).gif

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class minPath {

public static int minPath(int [][] m) {

if(m==null || m.length==0 || m[0]==null || m[0].length ==0) {
return 0;
}

int row=m.length;
int col=m[0].length;
int[][] dp=new int[row][col];
dp[0][0] = m[0][0];

for(int i=1;i<row;i++) {
dp[i][0] = dp[i-1][0]+m[i][0];
}

for(int j=1;j<col;j++) {
dp[0][j] = dp[0][j-1]+m[0][j];
}

for(int i=1;i<row;i++) {
for(int j=1;j<col;j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+m[i][j];
}
}

return dp[row-1][col-1];
}

public static void main(String[] args){
int [][]arr = {
{2,5,3,5},
{7,1,3,4},
{4,2,1,6},
};
System.out.printf("最短路径:%d",minPath(arr));
}
}

执行

1
2
$ javac minPath.java && java minPath 
最短路径:18

[[Go 解决最短路径问题]]
[[PHP 解决最短路径问题]]

-------------本文结束感谢您的阅读-------------
0%