shortpaths.java

用迪杰斯特拉算法求解最短路径问题

package cn;

public class ShortPaths {
	int a[][]={{0,100,15,100,100,100},{2,0,100,100,10,30},{100,4,0,100,100,10},{100,100,100,0,100,100},{100,100,100,15,0,100},{100,100,100,4,10,0}};
	int s[][]=new int[6][6];
	int c[]=new int[6];
	int j=0;
	void Short(){
		 for(int i=0;i<6;i++){
			 c[i]=a[0][i];//将一开始的数值加入
		 for(j=0;j<6;j++){
             for(int k=1;k<6;k++){
                	 if(c[k]+a[k][i]<=c[i]){
                		 c[i]=c[k]+a[k][i];
                	     s[i][k]=1;
                	     for(int j=0;j<k;j++){
                	    	 s[i][j]=s[k][j];
                	     }
                	     }
             }
		 } 
	   }
	 } 
	void print(){
		System.out.println("以下矩阵a[i][j]表示到达第i个点经历的点j：");
		for(int i=0;i<6;i++){
			 for(int j=0;j<6;j++){
				 System.out.print(s[i][j]+"  ");
			 }
		     System.out.println("");
	}
		for(int x=0;x<6;x++){
			System.out.println("到第"+x+"个点的最短距离是： "+c[x]);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自动生成方法存根
		 ShortPaths m=new  ShortPaths();
		 m.Short();
		 m.print();
	}

}