用动态规划算法求解最短路线问题

     问题如下：设有一个旅行者从A点出发，途中要经过B，C，D等处，最后到达E，从A到E有很多条路线可走，各个点的距离如下，问旅行者应该选择哪一条，是使A到E路线最短。

  求解算法：

public class Dp{
	private int[][] matrix;
	private int[] distance;//记录到终点的距离
	
	public  int[][] getMatrix(){
		return matrix;
		
	}
	public void  setMatrix(int[][] matrix){
		this.matrix = matrix;

	}
	/**任意两点之间的距离，前提是pointA<pointB
	  * @param PointA 起点
    	  * @param PointB 终点
	  */	
	public void  getMinDistanceBetweenPionts(int pointA,int pointB)
	{
		//初始化
		distance = new int[pointB+1];
		for(int i = 0 ;i<distance.length;i++) distance[i]=10000;
		distance[pointB] = 0;//该初始化保证(pointB,pointB)的距离为0

;		for(int i =pointB ;i>= pointA ;i--){//从最后pointB行开始,递减直到pointA
		
			for(int j = i+1;j <= pointB;j++){//历遍(i,i)->(i,pointB)，找到(i,pointB)的最小距离
				if( matrix[i][j] != 10000){
						int value  =0;
						if( j+1<= pointB) value = distance[j]; 
						int minDistance = matrix[i][j] +value;//最小路径为（i,j)的距离加(j，point)的距离
						if(minDistance <distance[i]) distance[i] = minDistance;//
				}
			}
		}		
	
		for(int i: distance)
		{
			System.out.print(" "+i);
		}
		System.out.println();
	}
	
	public static void main(String args[]){
		int m = 10000;
		int[][] matrix = {
						  {m,2,5,3,m,m,m,m,m,m},
						  {0,m,m,m,7,5,6,m,m,m},
						  {0,0,m,m,3,4,2,m,m,m},
						  {0,0,0,m,5,1,5,m,m,m},
						  {0,0,0,0,m,m,m,1,4,m},
						  {0,0,0,0,0,m,m,6,3,m},
						  {0,0,0,0,0,0,m,3,3,m},
						  {0,0,0,0,0,0,0,m,m,3},
						  {0,0,0,0,0,0,0,0,m,4},
						  {0,0,0,0,0,0,0,0,0,m}
						};
		Dp dp = new Dp();
		dp.setMatrix(matrix);
		dp.getMinDistanceBetweenPionts(0,9);
	}

}
		

 

 分析：

 

 1、找出状态转移公式；i 到 j 的最短距离等 （i，i+1)的距离 加上 （i+1，j)的最短距离

 2、保存每个点到 j 的最短距离的变量 distance[]

 

 这是我的想法，不知道大家有没有更好的算法，能缩短时间，欢迎大家讨论！