最短距離

距離"-1"はエッジなしに相当

public class WarshallFloyd {
	
	public static int[][][] WFshortestDist(int[][] a){
		int n=a.length;
		
		int[][] dist=StatUtilsX.MiscUtilX.DeepCopyInt2(a);
		int[][] pred=new int[n][n];
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(dist[i][j]>0){
					pred[i][j]=j;
				}else{
					pred[i][j]=-1;
				}
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				for(int k=0;k<n;k++){
					if(dist[i][k]<0 || dist[j][k]<0){
						
					}else if(dist[i][j]<0){
						dist[i][j]=dist[i][k]+dist[j][k];
						pred[i][j]=pred[i][k];
					}else if(dist[i][j]>dist[i][k]+dist[j][k]){
						dist[i][j]=dist[i][k]+dist[j][k];
						pred[i][j]=pred[i][k];
					}
				}
			}
		}
		int[][][] ret =new int[2][n][n];
		ret[0]=dist;
		ret[1]=pred;
		return ret;
	}

}

public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		int n=1000;
		int x=n*(n-1)/2;
		int[] data=new int[x];
		int max=2;
		for(int i=0;i<x;i++){
			data[i]=(int)(Math.random()*max);
			if(data[i]==0){
				data[i]=-1;
			}
		}
		int[][] dist=new int[n][n];
		int a=0;
		int b=1;
		for(int i=0;i<x;i++){
			dist[a][b]=data[i];
			dist[b][a]=data[i];
			b++;
			if(b==n){
				a++;
				b=a+1;
			}
		}
		/*
		for(int i=0;i<dist.length;i++){
			for(int j=0;j<dist[i].length;j++){
				System.out.print(dist[i][j]+"\t");
			}
			System.out.println();
		}
		*/
		int[][][] ans=WarshallFloyd.WFshortestDist(dist);
		System.out.println("dist");
		/*
		for(int i=0;i<ans[0].length;i++){
			for(int j=0;j<ans[0][i].length;j++){
				System.out.print(ans[0][i][j]+"\t");
			}
			System.out.println();
		}
		*/
		/*
		System.out.println("predecessor");
		for(int i=0;i<ans[1].length;i++){
			for(int j=0;j<ans[1][i].length;j++){
				System.out.print(ans[1][i][j]+"\t");
			}
			System.out.println();
		}
		*/


	}