import java.util.*;

public class Dijkstra {

    // Dijkstra doesn't work for Graphs with negative weight cycles. Because Dijkstra only focus on the
    // path from start vertex to others, but the negative weight cycles may not contain it.

    final static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        List<Edge> edges = new ArrayList<>();

        /*
                    Graph with no negative weight cycles
                       >(1)
                      /  | \
                    2/     |  \3
                    /    |   \
                    (0)     |5   > (2)
                     \     |   /
                     8\  |  / 3
                       \ v /
                        >(3)<
                         |
                         |
                        >(4)
                         |
                         |
                        >(5)
        */

        edges.add(new Edge(0, 1, 2));
        edges.add(new Edge(0, 3, 8));
        edges.add(new Edge(1, 2, 3));
        edges.add(new Edge(1, 3, 5));
        edges.add(new Edge(2, 3, 3));
        edges.add(new Edge(3, 4, 3));
        edges.add(new Edge(4, 5, 1));

        search(edges, 6, 0, 5);
        System.out.println("------------------------------------------------------");
        search(edges, 7, 0, 6);

        System.out.println("\n####################################################");
        System.out.println("Graph contains negative weight cycle");
        System.out.println("####################################################\n");

        edges.clear();

        /*
                    Graph with no negative weight cycles
                       >(1)
                      /  A \
                    2/     |  \3
                    /    |   \
                  (0)     |-8   > (2)
                     \     |    /
                     8\  |   / 3
                       \ |  /
                        >(3)<
                         |
                         |
                        >(4)
                         |
                         |
                        >(5)
        */

        edges.add(new Edge(0, 1, 2));
        edges.add(new Edge(0, 3, 8));
        edges.add(new Edge(1, 2, 3));
        edges.add(new Edge(3, 1, -8));
        edges.add(new Edge(2, 3, 3));
        edges.add(new Edge(3, 4, 3));
        edges.add(new Edge(4, 5, 1));

        search(edges, 6, 0, 5);
        System.out.println("------------------------------------------------------");
        search(edges, 7, 0, 6);
    }

    public static int search(List<Edge> edges, int n, int start, int end) {
        List<Integer> visited = new LinkedList<>();

        int[][] weights = new int[n][n];

        // Initialized with largest integer which represents no direct path from vertex a to b.
        for (int i = 0; i < n; i++) {
            Arrays.fill(weights[i], INF);

            weights[i][i] = 0;
        }

        for (Edge edge : edges) {
            weights[edge.start][edge.end] = edge.weight;
        }

        // used to keep the visiting path
        Map<Integer, String> detailedPath = new HashMap<>();

        // The path from start to x with smallest weight, where x means other points.
        int[] smallestWeightPath = new int[n];
        for (int i = 0; i < n; i++) {
            smallestWeightPath[i] = weights[start][i];
            detailedPath.put(i, start +"");
        }

        visited.add(start);

        while (visited.size() < n) {

            // Get the closest vertex to start point which is not visited yet. It will serve as
            // the intermediate vertex through which start point can link to other vertexes.
            int interVertex = getClosestUnvisited(visited, smallestWeightPath);

            // Stop searching if no appropriate vertexes found.
            if (interVertex == -1) {
                break;
            }

            // if vertex interVertex served as intermediate vertex, set it visited because all the
            // possible links through interVertex are traversed.
            visited.add(interVertex);

            for (int j = 0; j < n; j++) {

                // the same vertex or not linked
                if (interVertex == j || weights[interVertex][j] == INF) {
                    continue;
                }

                // move to j from start through intermediate vertex interVertex
                int tmp = smallestWeightPath[interVertex] + weights[interVertex][j];
                if (smallestWeightPath[j] > tmp) {
                    smallestWeightPath[j] = tmp;

                    detailedPath.put(j, detailedPath.get(interVertex) + "-->" + j);
                }
            }
        }

        if (smallestWeightPath[end] != INF) {
            System.out.println("From " + start + " to " + end + ", the smallest weight path " + detailedPath.get(end) + ", total weight is " + smallestWeightPath[end]);
        } else {
            System.out.println("From " + start + " to " + end + ", no path exists");
        }

        return smallestWeightPath[end];
    }

    private static int getClosestUnvisited(List<Integer> visited, int[] shortestPath) {
        int idx = -1;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < shortestPath.length; i++) {
            if (visited.contains(i)) {
                continue;
            }

            if (shortestPath[i] < min) {
                min = shortestPath[i];
                idx = i;
            }
        }

        return idx;
    }

    static class Edge {
        int start = 0;
        int end = 0;
        int weight = 0;

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-22 15:38:44

results matching ""

    No results matching ""