Implementation of the Dijkstra’s and Floyd-Warshall’s Algorithms

ShortestPath.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Scanner;

public class ShortestPath {

    static DiGraph g;
    static double d[];
    static int path[];
    static int source;
    static ArrayList<Integer> V = new ArrayList<>();
    static ArrayList<Integer> S = new ArrayList<>();

    private static int min(double[] d, DiGraph g, ArrayList<Integer> V) {
        int minIndex = -1;
        boolean initial = true;
        for (int v : V) {
            if (initial) {
                minIndex = v;
                initial = false;
            } else if (d[minIndex] > d[v]) {
                minIndex = v;
            }
        }
        return minIndex;
    }

    private static void getPath(int destination) {
        if (path[destination] != -1) {
            getPath(path[destination]);
            System.out.print("-> " + path[destination]);
        }
    }

    public static void main(String[] args) {
        g = new DiGraph();
        djikstra();
        floydWarshall();

    }

    private static void djikstra() {
        System.out.println("--------------- Djikstra Algorithm ---------------");
        g.vertices.stream().forEach((v) -> {
            V.add(v);
        });
        source = g.source;
        // initialization 
        S.add(source);
        V.remove(source);

        d = new double[g.vertices.size()];
        path = new int[d.length];
        Arrays.fill(path, -1);
        for (int v : V) {
            d[v] = g.getWeight(source, v);
        }
        d[source] = 0;
        System.out.println("");
        System.out.print("Iteration\t\tS\t\t\tw\t\t");
        for (int i = 1; i < d.length; i++) {
            System.out.printf("d[%d]\t\t", i);
        }
        System.out.println("");
        System.out.printf("Initial\t\t\t%-20s\t-\t\t", S);
        for (int i = 1; i < d.length; i++) {
            if (d[i] == Double.MAX_VALUE) {
                System.out.printf("%3c\t\t",'\u221e');

            } else {
                System.out.printf("%.1f\t\t", d[i]);

            }
        }
        System.out.printf("\n");

        int iteration = 0;
        int w = -1;
        while (!V.isEmpty()) {
            w = min(d, g, V);
            V.remove(Integer.valueOf(w));
            S.add(w);
            for (int v : V) {
                if (d[v] > d[w] + g.getWeight(w, v)) {
                    d[v] = d[w] + g.getWeight(w, v);
                    path[v] = w;
                }
            }
            iteration++;
            System.out.printf("%d\t\t\t%-20s\t%d\t\t", iteration, S.toString(), w);

            for (int i = 1; i < d.length; i++) {
                if (d[i] == Double.MAX_VALUE) {
                    System.out.printf("+INF\t\t", d[i]);

                } else {
                    System.out.printf("%.1f\t\t", d[i]);
                }
            }
            System.out.println("");

        }
        System.out.println(Arrays.toString(path));
        System.out.println("---------- Paths ----------");
        for (int v : g.vertices) {
            if (v != source) {
                System.out.print(source + " ");
                getPath(v);
                System.out.println("-> " + v);
            }
        }
    }
    static double[][] D;
    static int[][] floydWarshallPaths;

    private static void floydWarshall() {
        D = new double[g.vertices.size()][g.vertices.size()];
        floydWarshallPaths = new int[D.length][D.length];
        for (int[] path : floydWarshallPaths) {
            Arrays.fill(path, -1);
        }
        for (int i = 0; i < D.length; i++) {
            for (int j = 0; j < D.length; j++) {
                D[i][j] = g.getWeight(i, j);
                if (D[i][j] == Double.MAX_VALUE) {
                    System.out.print("+INF ");
                } else {
                    if (D[i][j] != 0) {
                        floydWarshallPaths[i][j] = j;
                    }
                    System.out.printf("%.0f ", D[i][j]);
                }

            }
            System.out.println("");
        }
        System.out.println("---------------------");

        for (int k = 0; k < D.length; k++) {
            for (int i = 0; i < D.length; i++) {
                for (int j = 0; j < D.length; j++) {
                    if (D[i][j] == Double.MAX_VALUE) {
                        System.out.printf("%-2c ", '\u221e');
                    } else {
                        System.out.printf("%-2.0f ", D[i][j]);
                    }
                }
                System.out.println();
            }
            System.out.println("---------------------");

            for (int i = 0; i < D.length; i++) {
                for (int j = 0; j < D.length; j++) {
                    if (D[i][j] > D[i][k] + D[k][j]) {
                        D[i][j] = D[i][k] + D[k][j];
                        floydWarshallPaths[i][j] = floydWarshallPaths[i][k];
                    }
                }
            }
        }
        for (int path[] : floydWarshallPaths) {
            for (int p : path) {
                System.out.printf("%d ", p);
            }

            System.out.println("");
        }
        for (int i = 0; i < D.length; i++) {
            for (int j = 0; j < D.length; j++) {
                System.out.println("Path from " + i + " to " + j + ": " + floydPath(i, j));

            }
        }
    }

    static ArrayList<Integer> floydPath(int u, int v) {
        ArrayList<Integer> path = new ArrayList<>();
        if (floydWarshallPaths[u][v] == -1) {
            return path;
        }
        path.add(u);
        while (u != v) {
            u = floydWarshallPaths[u][v];
            path.add(u);
        }
        return path;
    }
}

class DiGraph {

    public ArrayList<Integer> vertices = new ArrayList<>();
    public ArrayList<Cell> adjacencyList[];
    int source;

    double getWeight(int u, int v) {

        int index = adjacencyList[u].indexOf(new Cell(v, -1));
        if (u == v){
            return 0;
        }
        else if (index != -1) {
            return adjacencyList[u].get(index).weight;
        } else {
            return Double.MAX_VALUE;
        }
    }

    public DiGraph() {
        Scanner s = new Scanner(System.in);
        System.out.print("source vertex: ");
        source = s.nextInt();
        System.out.print("Enter vertices number: ");
        int verticesNbr = s.nextInt();
        adjacencyList = new ArrayList[verticesNbr];
        for (int u = 0; u < verticesNbr; u++) {
            adjacencyList[u] = new ArrayList<>();
            vertices.add(u);
            System.out.printf("Enter vertices adjacent to node %d including weight(double) [-1 to stop ]: ", u);
            int vertex;
            while ((vertex = s.nextInt()) != -1) {
                double w = s.nextDouble();
                if (w <= 0) {
                    throw new InputMismatchException("Cannot have negative weights for edges");
                }
                adjacencyList[u].add(new Cell(vertex, w));

            }

        }
    }

    class Cell {

        int vertex;
        double weight;

        public Cell(int vertex, double weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Cell) {
                return vertex == ((Cell) obj).vertex;
            }
            return super.equals(obj);
        }

        @Override
        public String toString() {
            return "v: " + vertex + ", w:" + weight;
        }

    }
}

[image: image.png]

…

On Fri, 22 Nov 2019 at 15:58, Bassanelli Francesco ***@***.***> wrote: I can't find the implementation of the "getWeight" method in the DIGraph class. Can you help me ? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <https://gist.github.com/8eb73e540fd116ffcaf8d641f372c665?email_source=notifications&email_token=ACOTTA7YFUN2TICRZTLNJKTQU7XRNA5CNFSM4JQR4VU2YY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF4UBI#gistcomment-3090452>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACOTTA6GKMA75MFD6B2LRVTQU7XRNANCNFSM4JQR4VUQ> .