ShortestPathGraph.java

/**********Graph.java**********/

import java.util.*;

public class Graph { 

    int size;
    ArrayList<Integer>[] graph;  

    public Graph(int vertices){ 

        this.size = vertices; 

        graph = new ArrayList[size]; 

        for(int i = 0; i < size; i++) 
        { 
            graph[i] = new ArrayList<>(); 
        } 
    }

    public void addEdge(int u, int v) 
    { 
        if(!graph[u].contains(v)){
            graph[u].add(v);  
        }
        if(!graph[v].contains(u)){
            graph[v].add(u);  
        }
    } 

    public ArrayList<Integer> getEdge (int val) {
        return graph[val];
    }

    public void printGraph(){
        for(int i = 0; i<size;i++){
            System.out.println(i + "   " + graph[i]);
        }
    }

    public ArrayList<Integer> findShortestPath(int source, int dest)  
    { 

        ArrayList<ArrayList<Integer> > paths = new ArrayList<ArrayList<Integer>>(); 

        ArrayList<Integer> sourcePath = new ArrayList<>();
        sourcePath.add(source);
        paths.add(sourcePath); 

        boolean destFound = false;

        while(!destFound){
            int largestPath = 0;
            for(int i = paths.size()-1; i >= 0 ; i--){
                if(paths.get(i).size() > largestPath)
                    largestPath = paths.get(i).size();
                if(paths.get(i).size() == largestPath){
                    ArrayList<Integer> tempPath= paths.get(i);
                    int lastVert = tempPath.get(tempPath.size()-1);
                    ArrayList<Integer> connections = getEdge(lastVert);
                    for(int j = 0; j < connections.size(); j++){
                        ArrayList<Integer> dup = new ArrayList<>();
                        for(int l = 0; l < tempPath.size(); l++){
                            dup.add(tempPath.get(l));
                        }
                        dup.add(connections.get(j));
                        paths.add(dup);
                    }
                }
            }
            for(ArrayList<Integer> path: paths){
                if(path.contains(dest)){
                    destFound = true;
                }
            }
        }

        for(ArrayList<Integer> path: paths){
            if(path.contains(dest)){
                return path;
            }
        }

        return sourcePath;
    }

}

/**********Driver.java**********/

import java.util.*;

public class Driver {
    public static void main(String[] args) {
        Graph g = new Graph(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<g.size;i++){
            System.out.println(i + "  " + g.getEdge(i));
        }
        
        int source = 2, dest = 6;
        System.out.println("Shortest Path (Length " + (g.findShortestPath(source, dest).size()-1) + ") : " + g.findShortestPath(source, dest));
        
        //g.printGraph();

    }
    
}