Class BellmanFord

contents/algorithm/code/BellmanFordTest.java:21–93

}

class BellmanFord {
    private int N;
    private ArrayList<Edge> edges;

    private final static int INF = Integer.MAX_VALUE;
    private int[] D;

    public BellmanFord(int N) {
        this.N = N;
        edges = new ArrayList<>();
        D = new int[N+1];
    }

    public void addEdge(int from, int to, int weight) {
        edges.add(new Edge(from, to, weight));
    }

    public void printEdges() {
        for (Edge edge : edges) System.out.println(edge);
    }

    public void getShortestDistance(int S) {
        /* init */
        for (int i = 1; i <= N; i++) {
            if (i != S) D[i] = INF;
        }

        /* Bellman-Ford */
        boolean negCycle = false;
        for (int i = 1; i <= N; i++) {
            for (Edge edge : edges) {
                int from = edge.from;
                int to = edge.to;
                int weight = edge.weight;
                if (D[from] != INF && D[to] > D[from] + weight) {
                    if (i == N) {
                        negCycle = true;
                        break;
                    }
                    D[to] = D[from] + weight;
                }
            }
        }

        if (negCycle) System.out.println("음의 사이클이 존재합니다.");
        else printDistance();
    }

    private void printDistance() {
        for (int i = 1; i <= N; i++) {
            if (D[i] == INF) System.out.print("∞ ");
            else System.out.print(D[i] + " ");
        }
        System.out.println();
    }

    static class Edge {
        private int from;