ShortestWeightedPath.java

/********************************wGraph.java********************************/

import java.util.*;

public class wGraph { 

    int size;
    ArrayList<Edge>[] graph;  

    public wGraph(int vertices){ 

        this.size = vertices; 

        graph = new ArrayList[size]; 

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

    public void addEdge(int s, int d, int w) 
    {
        boolean forward = false;
        for(Edge e : graph[s]){
            if(e.dest == d)
                forward = true;
        }
        boolean backward = false;
        for(Edge e : graph[d]){
            if(e.dest == s)
                forward = true;
        }
        if(!forward){
            Edge edge = new Edge(s,d,w);
            graph[s].add(edge);
        }
        if(!backward){
            Edge edge = new Edge(d,s,w);
            graph[d].add(edge); 
        }
    } 

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

    public void printGraph(){
        for(int i = 0; i<size;i++){
            System.out.print(i);
            for(Edge e : graph[i]){
                System.out.print("  |  " + e.dest + " weight: " + e.weight);
            }
            System.out.println();
        }
    }

    public void findShortestPath(int source, int destination)  
    { 

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

        for(Edge e: getEdge(source)){
            ArrayList<Edge> sourcePath = new ArrayList<>();
            sourcePath.add(e);
            paths.add(sourcePath);
        } 

        boolean foundAllPaths = false;

        boolean reachedDest = false;

        while(!foundAllPaths){

            boolean foundNewPath =  false;

            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<Edge> tempPath= paths.get(i);
                    int lastVert = tempPath.get(tempPath.size()-1).dest;
                    ArrayList<Edge> connections = getEdge(lastVert);
                    for(int j = 0; j < connections.size(); j++){
                        ArrayList<Edge> dup = new ArrayList<>();
                        for(int l = 0; l < tempPath.size(); l++){
                            dup.add(tempPath.get(l));
                        }
                        boolean temp = false;
                        for(Edge e : dup){
                            if(e.source == connections.get(j).dest || e.dest == connections.get(j).dest){
                                temp = true;
                            }
                        }
                        if(!temp){
                            dup.add(connections.get(j));
                            paths.add(dup);
                            foundNewPath = true;
                        }
                    }
                }
            }

            if(!foundNewPath){
                foundAllPaths=true;
            }

        }

        ArrayList<ArrayList<Edge> > finalPaths = new ArrayList<ArrayList<Edge>>(); 
        ArrayList<Integer> weights = new ArrayList<Integer>();
        
        for(ArrayList<Edge> path : paths){
            if(path.get(path.size()-1).dest == destination){
                finalPaths.add(path);
            }
        }

        for(int i = 0; i < finalPaths.size(); i++){
            int weight=0;
            for(Edge e : finalPaths.get(i)){
                weight += e.weight;
            }
            weights.add(weight);
        }
        
        int minWeightIndex = 0;
        for(int i = 0; i < weights.size(); i++){
            if(weights.get(i)<weights.get(minWeightIndex)){
                minWeightIndex = i;
            }
        }
        
        System.out.print("Shortest Path From " + source + " to " + destination + " Considering Weight: ");
        System.out.print(finalPaths.get(minWeightIndex).get(0).source);
        for(Edge e:finalPaths.get(minWeightIndex)){
            System.out.print("->"+e.dest);
        }
        
        System.out.println(" (Weight: " + weights.get(minWeightIndex) + ")");

    }
}

/********************************Edge.java********************************/


public class Edge
{
    int source;
    int dest;
    int weight;

    public Edge(int s, int d, int w)
    {
        this.source = s;
        this.dest = d;
        this.weight = w;
    }


}

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

import java.util.*;

public class Driver {
    public static void main(String[] args) {
        wGraph graph = new wGraph(6);
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 3);
        graph.addEdge(1, 3, 2);
        graph.addEdge(1, 2, 5);
        graph.addEdge(2, 3, 7);
        graph.addEdge(3, 4, 2);
        graph.addEdge(4, 0, 4);
        graph.addEdge(4, 1, 4);
        graph.addEdge(4, 5, 6);
        
        graph.printGraph();
        
        graph.findShortestPath(0,3);
        graph.findShortestPath(2,4);
        graph.findShortestPath(0,5);

    }
}