code: package graphTheory.algorithms.shortestDistance.arcCost;
  
  import graphTheory.algorithms.Algorithm;
  import graphTheory.graph.Arc;
  import graphTheory.instances.Instance;
  import graphTheory.instances.shortestPath.ArcShortestPathOneDestinationInstance;
  import graphTheory.utils.FibonacciHeap;
  
  import java.util.HashMap;
  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.List;
  
  /**
   * Implementation of the dijkstra algorithm. This algorithm compute the shortest
   * path between all the nodes to a destination in a directed or undirected
   * graph.
   * 
   * This version is implemented with a Fibonacci Heap.
   * 
   * @author Watel Dimitri
   * 
   */
  public class ArcDijkstraOneDestinationAlgorithm extends Algorithm<ArcShortestPathOneDestinationInstance> {
  
  	/**
  	 * If true, do not compute the shortest paths, but only the costs of the
  	 * shortest paths
  	 */
  	protected boolean computeOnlyCosts;
  
  	/**
  	 * For each node v, this map contains the shortest path from v to the
  	 * destination
  	 */
  	protected HashMap<Integer, List<Arc>> shPs;
  
  	/**
  	 * For each node v, this map contains the cost of the shortest path from v
  	 * to the destination
  	 */
  	protected HashMap<Integer, Integer> costs;
  
  	public HashMap<Integer, List<Arc>> getShortestPaths() {
  		return shPs;
  	}
  
  	public HashMap<Integer, Integer> getCosts() {
  		return costs;
  	}
  
  	public void setComputeOnlyCosts(boolean computeOnlyCosts) {
  		this.computeOnlyCosts = computeOnlyCosts;
  	}
  
  	/**
  	 * Map linking every node to its distance to destination
  	 */
  	private HashMap<Integer, Integer> distanceToDestination;
  
  	/**
  	 * Map linking every node arc following this node in one lowest cost path.
  	 */
  	private HashMap<Integer, Arc> following;
  
  	/**
  	 * Fibonacci Heap linking every node to its distance to destination.
  	 */
  	private FibonacciHeap<Integer> fibTree;
  
  	/**
  	 * Map linking every node to its fibonacciHeapNode in the heap.
  	 */
  	private HashMap<Integer, FibonacciHeap<Integer>.FibonacciHeapNode<Integer>> nodes;
  
  	@Override
  	protected void computeWithoutTime() {
  
  		init();
  
  		Integer n;
  		while (!fibTree.isEmpty()) {
  			n = fibTree.removeMin().getData();
  			expandFrom(n);
  		}
  
  		costs = distanceToDestination;
  
  		if (!computeOnlyCosts)
  			shPs = computePaths();
  	}
  
  	/**
  	 * Init the parameters.
  	 */
  	private void init() {
  
  		distanceToDestination = new HashMap<Integer, Integer>();
  		following = new HashMap<Integer, Arc>();
  
  		fibTree = new FibonacciHeap<Integer>();
  		nodes = new HashMap<Integer, FibonacciHeap<Integer>.FibonacciHeapNode<Integer>>();
  
  		initDistances();
  	}
  
  	/**
  	 * Init the distance from every node to the destination: the destination is
  	 * at distance 0 from the destination and every other node is at infinite
  	 * distance until they are reached.
  	 */
  	private void initDistances() {
  		FibonacciHeap<Integer>.FibonacciHeapNode<Integer> fhn;
  		Integer n;
  		Iterator<Integer> it = instance.getGraph().getVerticesIterator();
  		while (it.hasNext()) {
  			n = it.next();
  			double d;
  			if (n.equals(instance.getDestination())) {
  				distanceToDestination.put(n, 0);
  				d = 0.0;
  			} else {
  				distanceToDestination.put(n, null);
  				d = Double.POSITIVE_INFINITY;
  			}
  
  			if (!computeOnlyCosts)
  				following.put(n, null);
  			fhn = fibTree.insert(n, d);
  			nodes.put(n, fhn);
  		}
  	}
  
  	/**
  	 * Read the output arc (directed or not) (n,v) of n and see if this arc can
  	 * reduce the distance from v to the destination.
  	 * 
  	 * @param n
  	 */
  	private void expandFrom(Integer n) {
  		Integer distanceToDestination = this.distanceToDestination.get(n);
  		if (distanceToDestination == null) // Infinite distance from the source.
  			return;
  
  		Integer input;
  		Arc a;
  
  		Iterator<Arc> it = instance.getGraph().getInputArcsIterator(n);
  		while (it.hasNext()) {
  			a = it.next();
  
  			input = a.getInput();
  			expand(distanceToDestination, a, input);
  		}
  
  		it = instance.getGraph().getUndirectedNeighbourEdgesIterator(n);
  		while (it.hasNext()) {
  			a = it.next();
  			input = instance.getGraph().getNeighbourNode(n, a);
  			expand(distanceToDestination, a, input);
  		}
  	}
  
  	/**
  	 * See if using a path of weight distanceToDestination, and the arc a, we
  	 * can reduce the distance from the node input to the destination.
  	 * 
  	 * @param distanceToDestination
  	 * @param a
  	 * @param input
  	 */
  	private void expand(Integer distanceToDestination, Arc a, Integer input) {
  		Integer dist = distanceToDestination + instance.getCost(a);
  		Integer nndN = this.distanceToDestination.get(input);
  		if ((nndN == null || nndN > dist)) {
  			FibonacciHeap<Integer>.FibonacciHeapNode<Integer> fhn = nodes
  					.get(input);
  			fibTree.decreaseKey(fhn, dist);
  			this.distanceToDestination.put(input, dist);
  			if (!computeOnlyCosts)
  				following.put(input, a);
  		}
  	}
  
  	/**
  	 * Using the map preceding compute and return the lowest cost path from all
  	 * nodes to the destination
  	 * 
  	 * @return the lowest cost path from all nodes to the destination
  	 */
  	private HashMap<Integer, List<Arc>> computePaths() {
  		HashMap<Integer, List<Arc>> paths = new HashMap<Integer, List<Arc>>();
  		Iterator<Integer> it = instance.getGraph().getVerticesIterator();
  		while (it.hasNext()) {
  			Integer v = it.next();
  			computePaths(v, paths);
  		}
  		return paths;
  	}
  
  	/**
  	 * Using the map preceding compute and return the lowest cost path from v to
  	 * the destination
  	 * 
  	 * @return the lowest cost path from v to the destination
  	 */
  	private List<Arc> computePaths(Integer v, HashMap<Integer, List<Arc>> paths) {
  		List<Arc> l = paths.get(v);
  		if (l != null)
  			return l;
  
  		if (v.equals(instance.getDestination())) {
  			l = new LinkedList<Arc>();
  		} else {
  			Arc a = following.get(v);
  			if (a == null)
  				l = null;
  			else {
  				l = new LinkedList<Arc>(computePaths(a.getOutput(), paths));
  				((LinkedList<Arc>) l).addFirst(a);
  			}
  		}
  		paths.put(v, l);
  		return l;
  	}
  
  	@Override
  	protected void setNoSolution() {
  		shPs = null;
  		costs = null;
  	}
  
  }
  