package path;import java.util.HashSet;public class BellmanFord {		private int MAX = Integer.MAX_VALUE;	private int  N  = 1024;	//顶点数 ， 边数 ， 起点	private int nodenum, edgenum, original;	//图的边	private Edge [] edge = new Edge[N];	//保存距离	private double [] dis = new double[N];	private int [] pre = new int[N];	/**	 * @function 	 * @return	 */	boolean calculate()	{		for(int i = 1; i <= nodenum; ++i) //初始化			dis[i] = (i == original ? 0 : MAX);		for(int i = 1; i <= nodenum - 1; ++i)			for(int j = 1; j <= edgenum; ++j)				//松弛				if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost){					dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;					pre[edge[j].v] = edge[j].u;				}				boolean flag = true; 				//判断是否含有负权回路				for(int i = 1; i <= edgenum; ++i)					if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost){						flag = false;						break;					}					return flag;	}	void print_path(int root) //打印最短路的路径（反向）	{		while(root != pre[root]){ //前驱			System.out.print(root + "-->");			root = pre[root];		}		if(root == pre[root])			System.out.print(root + "\n");	}	public boolean init(Edge [] edges){		try{			nodenum = edgenum = 0;			HashSet<Integer> vSet = new HashSet<Integer>();			for(int i = 1 ; i < edges.length ; ++i){				edgenum++;				edge[i] = edges[i];				vSet.add(edges[i].u);				vSet.add(edges[i].v);			}			nodenum = vSet.size();			return true;		}catch(Exception e){			e.printStackTrace();			return false;		}	}	private void calcShortestPath(int original){		this.original = original;		pre[original] = original;		if(calculate())			for(int i = 1; i <= nodenum; ++i){ //每个点最短路				System.out.print(dis[i] + "\n");				System.out.print("Path:");				print_path(i);			}		else			System.out.println("have negative circle\n");	}    public static void main(String [] args)	{    	BellmanFord bellman = new BellmanFord();    	    	Edge [] edges = new Edge [7];    	edges[1] = new Edge(1 , 2 , 2);    	edges[2] = new Edge(1 , 3 , 5);    	edges[3] = new Edge(4 , 1 , 10);    	edges[4] = new Edge(2 , 4 , 4);    	edges[5] = new Edge(4 , 2 , 4);	    	edges[6] = new Edge(3 , 4 , 2);	    	    	bellman.init(edges);    	bellman.calcShortestPath(1);	}    	}class Edge //边{	// u为边的前驱结点，v为后继结点（暂且用前驱、后继来说）	int u, v;	//边的权重	double cost;	public Edge(int u , int v , double cost){		this.u = u;		this.v = v;		this.cost = cost;	}}