dijkstra.java

/************Graph.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) + ")");

    }

    public int getWeight (int s, int d) {
        int weight = 0;
        ArrayList<Edge> edges = getEdge(s);

        for(Edge edge : edges){
            if(edge.dest == d){
                weight = edge.weight;
                break;
            }
        }

        return weight;
    }

    public void dijkstra (int source)
    {
        int distances[] = new int[size];
        Boolean examined[] = new Boolean[size]; 

        for (int i = 0; i < size; i++) { 
            distances[i] = Integer.MAX_VALUE; 
            examined[i] = false; 
        } 

        distances[source] = 0; 

        for (int j = 0; j < size - 1; j++) { 

            int min = Integer.MAX_VALUE;
            int index = -1; 

            for (int i = 0; i < size; i++) 
                if (examined[i] == false && distances[i] <= min) { 
                    min = distances[i]; 
                    index = i; 
                } 

            examined[index] = true; 

            for (int i = 0; i < size; i++){

                if (!examined[i] && getWeight(index,i) != 0 && distances[index] != Integer.MAX_VALUE && distances[index] + getWeight(index,i) < distances[i]) 
                    distances[i] = distances[index] + getWeight(index,i); 

            }

        } 

        System.out.println("Node \t Distance From " + source); 
        for (int i = 0; i < size; i++) 
            System.out.println(i + " \t " + distances[i]); 

    }

}

/*************************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) {
        /*

        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));

        */

        /*
        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);
        */
       
        wGraph graph = new wGraph(5);
        graph.addEdge(0, 1, 3);
        graph.addEdge(0, 3, 7);
        graph.addEdge(0, 4, 2);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 4);
        graph.addEdge(2, 3, 2);
        graph.addEdge(3, 4, 3);
        
        graph.printGraph();
        
        System.out.println();
        
        graph.dijkstra(0);

    }
}