Dijkstra using - Bag, Indexmin PriorityQueue

Dijkstra.java

/************************************************
    BAG - data structure to store vertices
*************************************************/

class Bag<Item extends Comparable<Item>> implements Iterable<Item> {
	
	private Node first;
	private int N;
	
	/************NODE CLASS************/
	
	private class Node{
		Item item; Node next;
		Node(Item k){
			this.item =k;
		}
	}
	
	/************isEmpty() IMPLEMENTATION************/
	
	private boolean isEmpty(){
		return N==0;
	}
	
	public int size(){return N;}
	
	/************	CONTAINS ************/
	
	public boolean contains(Item item){
		Node current = first;
		if(isEmpty()) return false;
		while(current != null){
			if(current.item.equals(item)){
				return true;
			}
			current = current.next;
		}
		return false;
	}
	
	
	/************ADD IMPLEMENTATION************/
	
	public void add(Item k){
		Node current = first;
		if(isEmpty()) { first = new Node(k);N++;return;}
		Node oldfirst = first;
		first = new Node(k);
		first.next = oldfirst;
		N++;
		return;		
	}
	
	/*********  DELETE IMPLEMENTATION ****************/
	
	public void delete(Item k){
		Node current = first;
		if(isEmpty()) return;
		
		Node previous = current;
		while(current != null){
			if(current.item.compareTo(k)==0) break;
			previous = current;			
			current = current.next;
		}
		
		if(current == first){first = first.next;return;}
		if(current == null) return;
		
		previous.next = current.next;
	}
	
	/************ITERATOR IMPLEMENTATION************/
	//returns an iterable list 
	public Iterator<Item> iterator(){
		return new ListIterator();
	}
	
	/************LIST ITERATOR CLASS ************/
	//making the datastructure iterable and returns an iterable list 
	private class ListIterator implements Iterator<Item>{

		private Node current = first;
		
		public boolean hasNext(){
			return current != null;
		}
		
		public Item next(){
			Item item = current.item;
			current = current.next;
			return item;
		}
		
		public void remove(){
			return;
		}
		
	}
}

/************************************************
    IndexMinPQ - Priority Queue which stores 
    just the minimum corresponding to a vertex
    and a global minimum can be extracted in - O(logV)
*************************************************/

class IndexMinPQ<Key extends Comparable<Key>> {
	
	private int N; 
	private int[] pq,qp;
	private Key[] keys;
	
	public IndexMinPQ(int cap){
		pq = new int[cap+1]; qp = new int[cap+1];
		keys = (Key[]) new Comparable[cap+1];
		for(int i=0; i<cap+1;i++)
			qp[i] =-1;
	}
	
	public boolean isEmpty(){return N==0;}
	public int size() { return N;}
	public boolean contains(int k){	return qp[k]!=-1;}
	
	public void insert(int k, Key key){
		N++; qp[k] = N; pq[qp[k]] = k;
		keys[k] = key;
		swim(N);
	}
	
	public void change(int k, Key key){
		Key current = keys[k];
		if(current.compareTo(key)>0){
			keys[k] = key; sink(k);
		} else if(current.compareTo(key)<0){
			keys[k] =key; swim(k);
		}
	}
	
	public Key min(){
		return keys[pq[1]];
	}
	
	public int delMin(){
		int indexOfMin = pq[1];
		exch(1,N--);
		sink(1);
		keys[pq[N+1]] = null;
		qp[pq[N+1]] = -1;
		return indexOfMin;		
	}
	
	private boolean greater(int i, int j){		
		return keys[pq[i]].compareTo(keys[pq[j]]) >0;
	}
	
	private void exch(int i, int j){
		int swap = pq[i]; pq[i]=pq[j]; pq[j]= swap;
		qp[pq[i]]=i; qp[pq[j]]=j;
	}
	
	private void swim(int k){
		while(k>1 && greater(k/2 , k)){
			exch(k/2,k); k = k/2;
		}
	}
	
	private void sink(int k){
		while(2*k<=N){
			int j = 2*k;
			if(j<N && greater(j,j+1)) j++;
			if(!greater(k,j)) break;
			exch(k,j);
			k=j;
		}
	}	
}

/************************************************
    DirectedEdge - which stores edge specific propoerites
*************************************************/

class DirectedEdge implements Comparable<DirectedEdge>{
	
	private final int v,w;
	private final double weight;
	
	public DirectedEdge(int v, int w, double weight){
		this.v = v; this.w = w; this.weight = weight;
	}
	
	public int to(){
		return w;
	}
	
	public int from(){
		return v;
	}
	
	public double weight(){
		return weight;
	}
	
	public String toString(){
		return String.format("%d - %d , %2.4f", v,w,weight);
	}

	@Override
	public int compareTo(DirectedEdge that) {
		if(this.weight > that.weight ) return 1;
		else if(this.weight < that.weight) return -1;
		else return 0;
	}

}

/************************************************
    EdgeWeightedDigraph - adjacency lists are used 
    to construct the graph for each vertex 
*************************************************/

class EdgeWeightedDigraph {
	
	private int V,E;
	private Bag<DirectedEdge>[] adj;
	
	public EdgeWeightedDigraph(int V){
		this.V = V; 
		adj = (Bag<DirectedEdge>[]) new Bag[V];
		for(int i=0; i<V; i++){
			adj[i] = new Bag<DirectedEdge>();
		}
	}
	
	public EdgeWeightedDigraph(Scanner scan){
		this(Integer.parseInt(scan.nextLine())); scan.nextLine();
		while(scan.hasNextLine()){
			String[] str = scan.nextLine().split(" ");
			int v = Integer.parseInt(str[0]),w = Integer.parseInt(str[1]);double weight = Double.parseDouble(str[2]);
			DirectedEdge e = new DirectedEdge(v,w,weight);
			addEdge(e);			
		}		
	}
	
	public void addEdge(DirectedEdge e){
		int v = e.from();
		adj[v].add(e);
		E++;
	}
	
	public Iterable<DirectedEdge> adj(int v){
		return adj[v];
	}
	
	public Iterable<DirectedEdge> edges(){
		Bag<DirectedEdge> alledges = new Bag<DirectedEdge>();
		for(int i=0; i<V; i++){
			for(DirectedEdge e:adj(i)){
				alledges.add(e);
			}
		}
		return alledges;
	}
	
	public int V(){return V;}
	public int E(){return E;}
	
	public String toString(){
		String str="";
		str+= "Vertices: "+ V+", Edges:" +E+"\n";
		for(int i=0; i<V; i++){
			str+= i +":";
			for(DirectedEdge e:adj[i]){
				int w = e.to(); double weight = e.weight();
				str+= "-("+w+","+weight+")";
			}			
			str+="\n";
		}		
		return str;
	}

}

/************************************************
    Dijkstra- Computes shortest path from a single
    source to all vertices - Relaxing edges is the 
    core step of the dijkstra's algorithm 
    Maximum number of edges pq can contain is E
    And for each extraction - finds minimum in logV
    Worst case - O(ElogV)
*************************************************/

public class Dijkstra{
  
  public DirectedEdge[] edgeTo;
  public double[] distTo;
  public IndexMinPQ<Double> pq;
  
  public Dijkstra(EdgeWeightedDigraph G, int s){
  
    edgeTo = new DirectedEdge[G.V()];
    distTo = new double[G.V()];
    pq = new IndexMinPQ<Double>(G.V());
    
    Arrays.fill(distTo, Double.NEGATIVE_INFINITY);
    distTo[s]=0;
    
    pq.insert(s,0.0);
    
    while(!pq.isEmpty()){    
      relax(G,pq.delMin());    
    }  
  
  }
  
  public void relax(EdgeWeightedDigraph G, int v){  
    for(DirectedEdge e:G.adj(v)){    
      int w = e.to();
      if(distTo[w]>distTo[v]+e.weight()){
        distTo[w] = distTo[v]+e.weight; edgeTo[w]=e;
        if(pq.contains(w)) pq.change(w,distTo[w]);
        else pq.insert(w,distTo[w]);        
      }    
    }    
  }
  
  public double distTo(int v){ return distTo[v];}
	
	public boolean hasPathTo(int v){
		return distTo[v]<Double.POSITIVE_INFINITY;
	}
	
	public Stack<DirectedEdge> pathTo(int v){
		
		if(!hasPathTo(v)) return null;
		
		Stack<DirectedEdge> path = new Stack<DirectedEdge>();
		for(DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]){
			path.push(e);
		}
		
		return path;
		
	}  

}