그래프 : 벨만 포드

벨만-포드 알고리즘

: 그래프에서 최단 거리를 구하는 알고리즘 -> 다익스트라, 벨만포드, 플로이드워셜 3가지가 존재

: 음수 가중치 에지가 있어도 수행할 수 있음

: 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음

 

시간 복잡도 : O(VE)

* V : 노드 수

* E : 에지 수

 

 

 

벨만-포드 핵심 이론

1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화

 

> 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현!

> 출발 노드는 0, 나머지 노드는 무한대로 초기화

> edge 클래스는 일반적으로 노드 변수 2개와 가중치 변수로 구성

 

 

 

2. 모든 에지를 확인해 정답 리스트 업데이트

> 최단 거리 리스트에서 업데이트 반복 횟수는 노드 개수 -1

>  노드 개수가 N이고 음수 사이클이 없을 때 특정 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1 이기 때문

> 모든 에지 E = (s, e, w)에서 다음 조건을 만족하면 업데이트 실행

> 업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리

 

업데이트 조건과 방법

D[s] != 무한대, D[e] > D[s] + w일때 D[e] = D[s] + w로 배열의 값 업데이트 

 

 

 

* 에지 1개 사용

-> D[1] + 8과 D[2]를 비교했을 때, D[2]가 더 크므로 D[2]에 D[1] + 8 = 0 + 8 = 8을 넣어줌

-> D[1] + 3과 D[3]을 비교했을 때, D[3]이 더 크므로 D[3]에 D[1] + 3 = 0 + 3 = 3을 넣어줌

-> 나머지는 무한대..

 

=> 0, 8, 3, 무한대, 무한대가 됨

 

* 에지 2개 사용

-> D[4], D[5]는 무한대이므로 시작 X

-> D[1] + 8과 D[2]를 비교했을 때, 둘이 8로 같으므로 유지

-> D[1] + 3과 D[3]을 비교했을 때, 둘이 3으로 같으므로 유지

-> D[3] + 7과 D[4]를 비교했을 때, D[4]이 더 크므로 D[4]에 D[3] + 7 = 3 + 7 = 10을 넣어줌

-> D[1] + 5과 D[5]을 비교했을 때, D[5]가 더 크므로 D[5]에 D[1] + 5 = 8 + 5 = 13을 넣어줌

 

=> 0, 8, 3, 10, 13이 됨

 

 

 

3. 음수 사이클 유무 확인하기

> 모든 에지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인

> 업데이트되는 노드가 있다면, 음수 사이클이 있다는 것 + 최단 거리를 찾을 수 없는 그래프라는 뜻이 됨

> 음수 사이클이 존재하면 이 사이클을 무한히 돌수록 가중치가 감소하므로 최단 거리를 구할 수 없음

 

 

-> D[4]가 업데이트됨

-> 음수 사이클이 존재하므로 최단거리를 구할 수 없음을 알 수 있음

---

백준 온라인저지 11657번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, M;
    static Edge edges[];
    static long distance[];

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 노드
        M = Integer.parseInt(st.nextToken()); // 에지

        edges = new Edge[M + 1];
        distance = new long[N + 1]; // 최단거리 배열
        Arrays.fill(distance, Integer.MAX_VALUE); // 최단거리 배열 무한대 초기화

        // 에지 리스트 저장
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            edges[i] = new Edge(s, e, t);
        }

        // 벨만-포드 알고리즘 수행
        distance[1] = 0;

        for(int i=1; i<N; i++) { // N-1 만큼 수행
            for(int j=0; j<M; j++) {
                Edge edge = edges[j];

                // 더 작은 최단거리 있으면 업데이트
                if(distance[edge.start] != Integer.MAX_VALUE) {
                    if(distance[edge.end] > distance[edge.start] + edge.time) {
                        distance[edge.end] = distance[edge.start] + edge.time;
                    }
                }
            }
        }

        // 음수 사이클 확인
        boolean isCycle = false;

        for(int i=0; i<M; i++) {
            Edge edge = edges[i];

            if(distance[edge.start] != Integer.MAX_VALUE && distance[edge.end] > distance[edge.start] + edge.time) {
                isCycle = true;
            }
        }

        if(!isCycle) {
            for(int i=2; i<=N; i++) {
                if(distance[i] == Integer.MAX_VALUE) {
                    System.out.println("-1");
                } else {
                    System.out.println(distance[i]);
                }
            }
        } else {
            System.out.println("-1");
        }


    }

}
class Edge {
    int start, end, time;

    public Edge(int s, int e, int t) {
        this.start = s;
        this.end = e;
        this.time = t;
    }
}