import java.util.ArrayList;
import java.util.HashMap;

public class Bellmann_Ford {

	public static void main(String[] args) {

		ArrayList<String> Vertices = new ArrayList<>();
		ArrayList<Edge> EdgeList = new ArrayList<>();

		// vertices
		Vertices.add("A");
		Vertices.add("B");
		Vertices.add("C");
		Vertices.add("D");

		// edges
		EdgeList.add(new Edge("A", "B", 3));
		EdgeList.add(new Edge("A", "D", 8));
		EdgeList.add(new Edge("B", "C", 1));
		EdgeList.add(new Edge("C", "A", -1));
//		EdgeList.add(new Edge("C", "A", -5));	// negative cycle case
		EdgeList.add(new Edge("C", "D", 2));

		// result
		HashMap<String, BFpair> result = new HashMap<>();

		String srcname = "A";

		for (String vname : Vertices) {
			BFpair bfp = new BFpair();
			if (vname.equals(srcname)) {
				bfp.csf = 0;
				bfp.psf = vname;
			} else {
				bfp.csf = Integer.MAX_VALUE;
				bfp.psf = null;
			}
			result.put(vname, bfp);
		}

		for (int i = 1; i <= Vertices.size() - 1; i++) {
			for (Edge edge : EdgeList) {
				String svname = edge.v1name;// source vertex
				String dvname = edge.v2name;// destination vertex
				int wt = edge.weight;

				BFpair sp = result.get(svname);// src pair
				BFpair dp = result.get(dvname);// dest pair

				if (sp.psf == null) {
		 			continue;
				} else if (sp.csf + wt < dp.csf) {
					dp.csf = sp.csf + wt;
					dp.psf = sp.psf + dvname;
				}

				result.put(dvname, dp);
			}
		}

		// check for cycle
		for (Edge edge : EdgeList) {
			String svname = edge.v1name;// source vertex
			String dvname = edge.v2name;// destination vertex
			int wt = edge.weight;

			BFpair sp = result.get(svname);// src pair
			BFpair dp = result.get(dvname);// dest pair

			if (sp.psf == null) {
				continue;
			} else if (sp.csf + wt < dp.csf) {
				System.out.println("negative cycle present");
				break;
//				dp.csf = sp.csf + wt;
//				dp.psf = sp.csf + dvname;
			}
			result.put(dvname, dp);
		}

		System.out.println(result);

	}

	public static class Edge {
		String v1name;
		String v2name;
		int weight;

		public Edge(String v1, String v2, int w) {
			this.v1name = v1;
			this.v2name = v2;
			this.weight = w;
		}
	}

	public static class BFpair {
		int csf;
		String psf;

		public String toString() {
			return " @ " + this.csf + " via " + this.psf;
		}
	}

}