벨만-포드 알고리즘

벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 어느 한 정점에서 나머지 정점까지 거리를 구하는 알고리즘입니다.
하지만 다익스트라와는 다르게 음수 가중치를 갖는 그래프에서도 동작을 하며, 음수 사이클을 찾아내는 기능도 가지고 있습니다.
이러한 장점을 갖는 대신에 알고리즘의 수행 시간은 일반적으로 다익스트라보다 느린 단점을 가지고 있습니다.
이 알고리즘의 기본적인 아이디어는 다익스트라와 비슷합니다.
dist배열을 만들어서 최단 거리에 근접하게 계속 갱신시켜주는 방식입니다.
하지만 우선순위 큐를 이용하여 간선에 연결된 정점의 최단 거리를 갱신하는 것이 아니라, 모든 정점의 최단 거리를 구할 때까지 모든 간선들을 여러 번 확인하여 최단 거리를 구한다는 것이 차이점입니다.

벨만 포드 알고리즘의 구현 방법은 다익스트라와 비슷한 전처리 과정으로 dist배열을 만들고, 시작 정점의 dist는 0으로 만든 뒤, 모든 간선을 확인하는 것입니다.
간선이 u->v이라면, dist[v]와 dist[u]+w[E] (간선의 가중치)를 비교하여 갱신해줍니다.
이러한 과정을 V번 반복하면 됩니다.
과정을 V번 반복하는 이유는 시작점에서 어떤 u까지 가는 간선의 개수는 최대 V-1개이고, 이러한 간선들이 불행하게도 한차례마다 한 간선씩 갱신이 된다고 해도 V-1번이면 찾을 수 있습니다.
그러면 왜 V-1번이 아니라 V번 반복할까요?
그 이유는 음수 사이클이 있을 경우 데이터 범위의 제한이 없을 경우 무한하게 갱신되기 때문입니다.
나머지 정상적인 경우 음수 사이클이 없을 경우에는 V-1번에 갱신되기 때문에 V번째 때 갱신이 되는 일이 없을 것입니다.
하지만 음수 사이클에 경우에는 V번째에 갱신이 되므로 이를 통하여 음수 사이클을 판별합니다.
이러한 특징은 새로운 최단 거리를 찾을 때마다 갱신해주는 다익스트라에서는 찾을 수 없는 특징입니다.

입력	출력
첫 줄에 정점의 개수 N과 간선의 개수 M, 그리고 시작 정점 S가 주어집니다. 다음 M줄에 간선의 관계 시작정점 u와 도착정점 v 그리고 간선 가중치 w가 주어집니다.	시작정점에서 각 정점사이의 거리를 모두 출력합니다. 만약 음수 사이클이 발견되면 -1을 출력합니다.
Sample Input	Sample Output
7  11  1 1  2  10 1  3  3 1  7  20 2  3  4 2  4  3 3  5  7 4  3  11 5  7  -1 6  5  -2 7  6  -3 6  4  2	-1

import java.util.*;

class Edge {
    int dst, weight;
    Edge(){}
    Edge(int dst, int weight) {
        this.dst = dst;
        this.weight = weight;
    }
}

public class Main {
    static Vector<Vector<Edge>> edge;
    static int n;
    static int m;
    static int s;
    private static int INF = 987654321;

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        s = scanner.nextInt();
        edge = new Vector<Vector<Edge>>();
        for (int i = 0; i < n + 1; i++) {
            Vector<Edge> e = new Vector<Edge>();
            edge.add(e);
        }
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int d = scanner.nextInt();
            Edge e = new Edge(v, d);
            edge.elementAt(u).add(e);
        }
        Vector<Integer> dist = bellmanFord(s);
        if (dist == null) {
            System.out.println(-1);
        }
        else {
            for (int i = 1; i < dist.size(); i++) {
                System.out.println(String.valueOf(dist.elementAt(i)));
            }
        }
    }

    public static Vector<Integer> bellmanFord(int cur) {
        Vector<Integer> upper = new Vector<Integer>();
        for (int i = 0; i <= n; i++) {
            if (i == cur) upper.add(0);
            else upper.add(INF);
        }
        boolean updated = false;
        for (int iter = 0; iter < n; iter++) {
            updated = false;
            for (int here = 1; here <= n; here++) {
                for (int i = 0; i < edge.elementAt(here).size(); i++) {
                    Edge a = edge.elementAt(here).elementAt(i);
                    int there = a.dst;
                    int nextdist = upper.elementAt(here) + a.weight;
                    if (upper.elementAt(there) > nextdist) {
                        upper.setElementAt(nextdist, there);
                        updated = true;
                    }
                }
            }
            if (!updated) break;
        }
        if (updated) return null;
        return upper;
    }
}