벨만포드란?

다익스트라와 목적은 같다. 한 시작 정점에서 다른 모든 노드까지의 최단 경로 거리를 구하는 것.

하지만, 다익스트라는 음의 간선이 있으면 정상작동하지 않는다.
벨만포드는 음의 간선까지는 허용한다. 하지만, 벨만포드도 음의 순환이 존재하는 그래프에 대해서는 정상 작동 하지 않는다.

원리

원리는 다음과 같다. 최단 경로 테이블에서 시작 노드를 0으로 잡고 나머지 노드는 INF로 잡는다. (상황에 따라 잘 조절할것. 항상 20억 이상으로 설정했다가 잘못하면 int 범위 넘을 수 있음.)

이후, 노드의 갯수 - 1번 반복하면서, 각 반복마다 모든 간선들을 활용해서 최단경로테이블을 업데이트한다.

이후 한번 더 간선들로 최단경로테이블을 순회하려고할 때 갱신되려는 정보가 있다면, 이 그래프에 음순환이 존재하는 것을 의미한다.

벨만포드는 간선의 정보가 중요하다. 그래서 Edge클래스를 만들고, 여기에 s,e,cost 정보를 담는다.

코드 (그래프가 연결그래프라는 보장이 없는경우)

이런 문제에서는 본래의 벨만포드가 갖고 있는 table[e.s] != INF 라는 조건을 제거해야한다. 이게 있다면, 시작정점과 연결되지 않은 모든 정점들은 평생 INF값을 갖게 되어서 초기화되지 않기 때문이다.
물론, 이렇게 구한다면, 시작정점과 같은 네트워크에 속하지 않은 정점들이 가진 테이블 값은 신뢰할 수 없는 쓰레기 값이다.
하지만, 그쪽 네트워크에서의 음의순환 존재 여부는 판단할 수 있게 해준다.

아래 예시는 INF를 문제조건에 따라 1억으로 잡았다.

    static boolean bellmanFord(int s) {
        int INF = 1_0000_0000;
        int[] table = new int[N + 1];
        Arrays.fill(table, INF);
        table[s] = 0;

        for (int i = 0; i < N - 1; i++) { // 정점개수-1번 반복
            for (Edge e : edges) {
                if (table[e.e] > table[e.s] + e.cost) { 
                // e로가는 방법이 현재까지의 s로가는 길에서 해당 간선 타고 가는게 더 빠른 경우
                    table[e.e] = table[e.s] + e.cost;
                }
            }
        }

        for (Edge e : edges) {
            if (table[e.e] > table[e.s] + e.cost) {
                return false; 
                // 마지막 한 바퀴에서 만약 갱신되려고 한다면 이는 음 순환이 있는 것임.
            }
        }

        return true;
    }

코드 (연결그래프라는 보장이 있는 경우)

    static boolean bellmanFord(int s) {
        int INF = 1_0000_0000;
        int[] table = new int[N + 1];
        Arrays.fill(table, INF);
        table[s] = 0;

        for (int i = 0; i < N - 1; i++) { // 정점개수-1번 반복
            for (Edge e : edges) {
                if (table[e.s] != INF && table[e.e] > table[e.s] + e.cost) { // e로가는 방법이 현재까지의 s로가는 길에서 해당 간선 타고 가는게 더 빠른 경우
                    table[e.e] = table[e.s] + e.cost;
                }
            }
        }

        for (Edge e : edges) {
            if (table[e.s] != INF && table[e.e] > table[e.s] + e.cost) {
                return false; // 마지막 한 바퀴에서 만약 갱신되려고 한다면 이는 음 순환이 있는 것임.
            }
        }

        return true;
    }

시간 복잡도

O((V-1)*E) -> O(VE)

V-1번만 반복하고, 이후 음순환존재여부를 판단해야한다는 것을 잊지말자.