Java 解决最短路径问题

最短路径问题

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

图解

代码

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));
    }
}

执行

$ javac minPath.java && java minPath 
最短路径：18

关联

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