import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BellmanFord {

    // Dijkstra doesn't support graphs with negative weight edges that forms cycles. But Bellman-Ford works
    // for such graphs which is also much simpler than Dijkstra and suites well for distributed systems.

    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, -7));
        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 void search(List<Edge> edges, int n, int start, int end) {
        Map<Integer, String> path = new HashMap<>();

        // lowestWeightPath from start to other n vertex
        long[] lowestWeightPath = new long[n];

        for (int i = 1; i < n; i++) {
            lowestWeightPath[i] = Integer.MAX_VALUE;
        }

        for (Edge edge : edges) {
            if (edge.start == start) {
                path.put(edge.end, start + "-->" + edge.end);
            }
        }

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

            // i means the times vertex edge.start has to serve as a intermediate vertex
            // through which vertex start gets to vertex edge.end.

            // We can imagine there are n * n edges, which means every pair vertex have connected
            // path. It degrades to Floyd algorithm.

            for (int j = 0; j < edges.size(); j++) {

                // edge serves as the intermediate path
                Edge edge = edges.get(j);

                // edge.start serves as the intermediate vertex
                if (lowestWeightPath[edge.end] > lowestWeightPath[edge.start] + edge.weight) {
                    lowestWeightPath[edge.end] = lowestWeightPath[edge.start] + edge.weight;

                    path.put(j, path.get(edge.start) + "-->" + j);
                }
            }
        }

        boolean containsNegativeWeightCycle = false;

        // check for negative-weight cycles.
        for (int i = 0; i < edges.size(); i++) {
            Edge edge = edges.get(i);

            if (lowestWeightPath[edge.end] > lowestWeightPath[edge.start] + edge.weight) {
                containsNegativeWeightCycle = true;

                break;
            }
        }

        if (containsNegativeWeightCycle) {
            try {
                throw new Exception("Graph contains negative weight cycle");
            } catch (Exception e) {
                e.printStackTrace();
            }
        } else if (lowestWeightPath[end] != INF) {
            System.out.println("From " + start + " to " + end + ", the lowest weight path " + path.get(end) + ", total weight is " + lowestWeightPath[end]);
        } else {
            System.out.println("From " + start + " to " + end + ", no path exists");
        }
    }

    static class Edge {
        public int start;
        public int end;
        public int weight;

        Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }
}

References

  1. https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-07 09:22:45

results matching ""

    No results matching ""