GraphsWShortest.java

import java.util.ArrayList;

public class Graphs {
	int numArrays;
	static ArrayList[] arr;
	String bestPath = "";
	int lengthPath = 0;
	static int min = Integer.MAX_VALUE;
	static ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
	static ArrayList<Integer> tempFirst = new ArrayList<Integer>();
	
	
	//constructor
	public Graphs(int numArrays) {
		this.numArrays = numArrays;
		arr = new ArrayList[numArrays];
		
		for(int i = 0;i< arr.length;i++) {
			arr[i] = new ArrayList<Integer>();
		}
		
	}
	
	public static void main(String[]args) {
		Graphs g = new Graphs(8);
		
		g.addEdge(0, 1); 
		g.addEdge(0, 3);
		g.addEdge(1, 2); 
		g.addEdge(3, 4);
		g.addEdge(3, 7);
		g.addEdge(4, 5); 
		g.addEdge(4, 6); 
		g.addEdge(4, 7); 
		g.addEdge(5, 6);
		g.addEdge(6, 7);
		
//		for(int i = 0;i<arr.length;i++) {
//			System.out.println(i + " :" + getEdge(i));
//		}
		
		tempFirst.add(2);//adding the source
		
		findShortest(tempFirst, 2, 6, 8, 0);
		
		System.out.println("The shortest path is " + shortestPath(paths));
//		for(int i = 0;i<paths.size();i++) {
//			System.out.println(paths.get(i));
//		}
		
	}//end main
	
	public static String shortestPath(ArrayList<ArrayList<Integer>> arr){
		String str = "";
		int maxVal = Integer.MAX_VALUE;
		int spot = 0;
		ArrayList<Integer> minimum = new ArrayList<Integer>();
		for(int i = 0;i<arr.size();i++) {
			if(arr.get(i).size()<maxVal) {
				maxVal=arr.get(i).size()+1;
				spot = i;
				//System.out.println(maxVal);
			}//end if
		}//end for
		minimum=arr.get(spot);
		for(int i = 0;i<minimum.size();i++) {
			str+=minimum.get(i) + " ";
		}
		return str;
	}
//	
	public static void findShortest(ArrayList<Integer> arr, int source, int destination, int size, int count) {
		
		ArrayList<Integer> arrEdges = getEdge(source);//getting all values from edge of source
	
		//System.out.println(arrEdges);
		
		for(int i = 0;i<arrEdges.size();i++) {
			ArrayList<Integer> temp = new ArrayList<Integer>();
			for(int j = 0;j<arr.size();j++) {
				temp.add(arr.get(j));//adding things
			}//end for
			if(arrEdges.get(i)==destination) {//if an edge == destination
				temp.add(destination);
				min=temp.size();
				//System.out.println(temp);
				paths.add(temp);
				return;//exit the call
			} else {//if you don't find the destination vertex among the edges
				if(count==size) {
					return;
				} else {
					temp.add(arrEdges.get(i));
					findShortest(temp, arrEdges.get(i), destination, size, count+1);
				}
			}//end else
		}//end for
		
		
		
//			//System.out.println(getEdge(source));
//			//base case
//			if(source==destination) {
//				arr.add(destination);
//				paths.add(arr);
//			} 
//			if(count<size) {
//				for(int i = 0;i<getEdge(source).size();i++) {
//					//System.out.println(letters[i]);
//					int num = getEdge(source).get(i);
//					if(num==destination) {
//						//System.out.println(letter);
//						arr.add(num);
//						paths.add(arr);
//						return;
//					} else {//if the source has the destination as a part of the getEdge string 
//						arr.add(num);
//						//System.out.println(letter);
//						findShortest(arr, num, destination, size, count+1);
//					}//else will check for other things
//				}//end for
//			}
	}//end method
	
	public void addEdge(int vertex1, int vertex2) {
		arr[vertex1].add(vertex2);
		arr[vertex2].add(vertex1);
	}//end method
	
	public static ArrayList<Integer> getEdge(int vertex) {
		ArrayList<Integer> numbers = new ArrayList<Integer>();
			for(int j = 0;j<arr[vertex].size();j++) {
				numbers.add((int)arr[vertex].get(j));
			}
			return numbers;
	}//end method
}