import java.util.HashMap;

import java.util.LinkedHashSet;

import java.util.Map;

import java.util.Set;

import java.util.TreeMap;

/**

* 음수 양수 Edge 에 대해서도 가능하다.

* Worst case: O(|V| |E|)

*

* @author Justin Wetherell <phishman3579@gmail.com>

*/

public class BellmanFord {

private static Map<Graph.Vertex<Integer>, Graph.CostVertexPair<Integer>> costs = null;

private static Map<Graph.Vertex<Integer>, Set<Graph.Edge<Integer>>> paths = null;

private static boolean containsNegativeWeightCycle = false;

private BellmanFord() { }

public static Map<Graph.Vertex<Integer>, Graph.CostPathPair<Integer>> getShortestPaths(Graph<Integer> g, Graph.Vertex<Integer> start) {

getShortestPath(g, start, null);

Map<Graph.Vertex<Integer>, Graph.CostPathPair<Integer>> map = new HashMap<Graph.Vertex<Integer>, Graph.CostPathPair<Integer>>();

for (Graph.CostVertexPair<Integer> pair : costs.values()) {

int cost = pair.getCost();

Graph.Vertex<Integer> vertex = pair.getVertex();

Set<Graph.Edge<Integer>> path = paths.get(vertex);

map.put(vertex, new Graph.CostPathPair<Integer>(cost, path));

}

return map;

}

public static Graph.CostPathPair<Integer> getShortestPath(Graph<Integer> g, Graph.Vertex<Integer> start, Graph.Vertex<Integer> end) {

if (g == null)

throw (new NullPointerException("Graph must be non-NULL."));

// Reset variables

costs = null;

paths = null;

containsNegativeWeightCycle = false;

paths = new TreeMap<Graph.Vertex<Integer>, Set<Graph.Edge<Integer>>>();

for (Graph.Vertex<Integer> v : g.getVerticies()) {

paths.put(v, new LinkedHashSet<Graph.Edge<Integer>>());

}

costs = new TreeMap<Graph.Vertex<Integer>, Graph.CostVertexPair<Integer>>();

for (Graph.Vertex<Integer> v : g.getVerticies()) {

if (v.equals(start))

costs.put(v, new Graph.CostVertexPair<Integer>(0, v));

else

costs.put(v, new Graph.CostVertexPair<Integer>(Integer.MAX_VALUE, v));

}

boolean negativeCycleCheck = false;

for (int i = 0; i < (g.getVerticies().size()); i++) {

// If it's the last vertices perform a negative weight cycle check.

// The graph should be

// finished by the size()-1 time through this loop.

if (i == (g.getVerticies().size() - 1))

negativeCycleCheck = true;

// Compute costs to all vertices

for (Graph.Edge<Integer> e : g.getEdges()) {

Graph.CostVertexPair<Integer> pair = costs.get(e.getToVertex());

Graph.CostVertexPair<Integer> lowestCostToThisVertex = costs.get(e.getFromVertex());

// If the cost of the from vertex is MAX_VALUE then treat as

// INIFINITY.

if (lowestCostToThisVertex.getCost() == Integer.MAX_VALUE)

continue;

int cost = lowestCostToThisVertex.getCost() + e.getCost();

if (cost < pair.getCost()) {

if (negativeCycleCheck) {

// Uhh ohh... negative weight cycle

System.out.println("Graph contains a negative weight cycle.");

containsNegativeWeightCycle = true;

return null;

}

// Found a shorter path to a reachable vertex

pair.setCost(cost);

Set<Graph.Edge<Integer>> set = paths.get(e.getToVertex());

set.clear();

set.addAll(paths.get(e.getFromVertex()));

set.add(e);

}

}

}

if (end != null) {

Graph.CostVertexPair<Integer> pair = costs.get(end);

Set<Graph.Edge<Integer>> set = paths.get(end);

return (new Graph.CostPathPair<Integer>(pair.getCost(), set));

}

return null;

}

public static boolean containsNegativeWeightCycle() {

return containsNegativeWeightCycle;

}

}