bellman_ford.java

算法导论上机作业java实现

import java.math.*;
//import java.lang.*;
public class Bellman_Ford {                      
	static int v = 5;          //the number of the point
	static int[] pi = new int [v];//这个说组是表示前驱节点pi[i]=j表示j是i的前驱节点
	static int[][] G = new int [v][v];//表示的是边的权值，G[i][j]=5表示边ij的权值为5
	static int[] d = new int [v];//一个额外的数组，用来表示节点的一个值
public static void Initial_single_source(){
	for(int i=1;i<v;i++){
		d[i] = Integer.MAX_VALUE;
		pi[i] = v;
	}
	d[0]=0;
}
public static void relax(){
	for(int i = 0;i<v;i++){
		for(int j=1;j<v;j++){
			if(G[i][j]!=0){
				if(d[j]>d[i]+G[i][j]){
					d[j] = d[i]+G[i][j];
					pi[j] = i;
					}
				//System.out.println(pi[j]);
			}
				
		}
	}
	
}
public static int Sub_Bellman(){
	Initial_single_source();
	relax();
	for(int i=0;i<v;i++){
		for(int j =0;j<v;j++){
			if(d[j]>d[i]+G[i][j])
				return -1;
		}
	}
	return 1;
}
	public static void main(String[] args) {
		//for(int i=0;i<v;i++){
			//for(int j = 1;j<v;j++){
			//System.out.println("if the edeg of ij didn't has connect,input 0;else input the weight");
			//System.out.println("input the weight of ij");
			//System.in.read(G[i][j]);
			//System.in.close();
			//}
		//}
		 for(int i =0;i<v;i++){
	    	   for(int j=0;j<v;j++)
	    		   G[i][j] = v;
       }
       G[0][1]=6;
       G[0][3]=7;
       G[1][2]=5;
       G[1][3]=8;
       G[1][4]=-4;
       G[2][1]=-2;
       G[3][2]=-3;
       G[3][4]=9;
       G[4][0]=2;
       G[4][2]=7;
       Sub_Bellman();
       for(int i=1;i<v;i++){
    	   if(pi[i]!=v){
    		   System.out.println("The single source of the shortest path is"+(pi[i])+"to"+i);
    	   }
       }
       
	}

}