Bellman Ford

From programming_contest
Jump to: navigation, search
 1 /**
 2  * Bellman Ford: finds shortest path in graphs with negative edges and possible minimum weight cycles
 3  * @param r start node
 4  * @param in adjacency list
 5  * @return distance to each node from start node
 6  */
 7 public int[] bellmanFord(int r, ArrayList<HashMap<Integer,Integer>> in){
 8 	int[] out=new int[in.size()],prev=new int[in.size()];
 9 	Arrays.fill(out, Integer.MAX_VALUE);
10 	out[r]=0;
11 	for(int i:in.get(r).keySet()){
12 		out[i]=in.get(r).get(i);
13 		prev[i]=r;
14 	}
15 	for(int i=0;i<in.size();i++)for(int j=0;j<in.size();j++)for(int k:in.get(j).keySet())if(out[j]+in.get(j).get(k)<out[k]){
16 		out[k]=out[j]+in.get(j).get(k);
17 		prev[k]=j;
18 	}
19 /*		this loop is only here to detect the negative weight cycles...if you don't have any you can use skip this or just use dijkstra
20 		for(int j=0;j<in.size();j++)for(int k:in.get(j).keySet())if(out[j]+in.get(j).get(k)<out[k]){
21 			//TODO Whatever you plan to do with a negative weight cycle
22 		}*/
23 	return out;//or you can return prev if you so choose
24 }