Node.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;


public class Node {
	private String value;
	private HashSet<Node> neighbours = new HashSet<Node>();

	public Node(String value, Collection<Node> neighbours){
		this.value = value;
		this.neighbours.addAll(neighbours);
		for(Node neighbour : neighbours){
			neighbour._add(this);
		}
	}

	public void add(Node node){
		this.neighbours.add(node);
		node._add(this);
	}

	public void _add(Node node){
		this.neighbours.add(node);
	}

	void printPaths(List<Node> dones, Set<Node> marked){
		marked.add(this);
		ArrayList<Node> newDones = new ArrayList<Node>(dones);
		newDones.add(this);
		HashSet<Node> remaindings = new HashSet<Node>(neighbours);
		remaindings.removeAll(marked);
		if (remaindings.isEmpty()) {
			System.out.println(newDones.toString());
		}else{
			for(Node node : neighbours){
				if( ! marked.contains(node)) {
					node.printPaths(newDones, marked);
				}
			}
		}
	}
	
	List<Node> getShortestPath(Node to){
		HashMap<Node, ArrayList<Node>> pathTo = new HashMap<Node, ArrayList<Node>>();
		Queue<Node> toProcess = new ArrayDeque<Node>();
		HashSet<Node> marked = new HashSet<Node>();
		ArrayList<Node> pathToThis = new ArrayList<Node>();
		pathToThis.add(this);
		pathTo.put(this, pathToThis);
		marked.add(this);
		Node current = this;
		while( ! to.equals(current)){
			for(Node neighbour : current.neighbours){
				if( ! marked.contains(neighbour)){
					marked.add(neighbour);
					toProcess.add(neighbour);
					ArrayList<Node> pathToNeighbour = new ArrayList<Node>(pathTo.get(current));
					pathToNeighbour.add(neighbour);
					pathTo.put(neighbour, pathToNeighbour);
				}
			}
			current = toProcess.poll();
		}
		return pathTo.get(to);
	}

	public String toString(){
		return value;
	}
	
    @Override
	public boolean equals(Object obj) {
	       if (!(obj instanceof Node))
	    	   return false;
	       if (obj == this)
	    	   return true;
	       Node rhs = (Node) obj;
	       return this.value.equals(rhs.value);
	}
	        
    @Override
    public int hashCode() {
    	return value.hashCode();
    }
    
	@SuppressWarnings("serial")
	public static void main(String[] args){
		final Node a = new Node("A", new ArrayList<Node>());
		final Node b = new Node("B", new ArrayList<Node>(){{this.add(a);}});
		final Node c = new Node("C", new ArrayList<Node>(){{this.add(b);}});
		final Node d = new Node("D", new ArrayList<Node>(){{this.add(b);}});
		new Node("E", new ArrayList<Node>(){{this.add(c);}});
		new Node("F", new ArrayList<Node>(){{this.add(d);}});
		final Node g = new Node("G", new ArrayList<Node>(){{this.add(a);}});
		final Node h = new Node("H", new ArrayList<Node>(){{this.add(g);}});
		final Node i = new Node("I", new ArrayList<Node>(){{this.add(a);}});
		new Node("J", 
						  new ArrayList<Node>(){{
								  this.add(i); this.add(h); }});

		a.printPaths( new ArrayList<Node>(),  new HashSet<Node>());
		
		System.out.println(a.getShortestPath(h).toString());
	}
}


//[A, G, H, J, I]
//[A, B, D, F]
//[A, B, C, E]
//[A, G, H]