밸만-포드 알고리즘

밸만-포드

---

• 최단 거리를 구하는 알고리즘입니다.

 

특징

---

• 음수 가중치 에지가 있어도 수행할 수 있습니다.
• 전체 그래프에서 음수 사이클의 존재 여부를 파악할 수 있습니다.
• O(nm) 시간 복잡도 가집니다.

 

핵심 이론

---

1. 에지 리스트로 그래프를 구현하고 경로 리스트 초기화하기
2. 모든 에지를 확인해 정답 리스트 업데이트하기
   • 업데이트 반복 횟수 = 노드 수 - 1

구성 형태

 

음수 사이클이 없을 경우, N-1 에지 사용 횟수를 사용하고 나면, 정답 리스트가 완성된다. 그리고 이렇게 완성된 후, 마지막으로 음수 사이클이 존재하는지 확인한다.

 

음수 사이클 유무 확인하기

---

• 모든 에지를 한 번씩 다시 사용해, 업데이트 되는 노드가 발생하는지 확인합니다.
• 업데이트 되는 노드가 있다면, 음수 사이클이 있다는 뜻이 되고, 최단 거리를 찾을 수 없다는 뜻입니다.

 

---

 

백준 11657번 - 타임머신

 

문제

 

여기서 핵심은 [N개의 도시 = 노드], [M개의 버스  = 간선], [A B C  = 출발 노드, 도착노드 , 가중치] 이러한 방식으로 생각하는 것입니다.

 

private static final int MAX_VALUE = Integer.MAX_VALUE;

static long[] min;
static ArrayList[] edge;

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int N = input.nextInt();
    int M = input.nextInt();
    min = new long[N + 1];
    edge = new ArrayList[M + 1];

    //그래프 세팅
    for (int i = 1; i < M + 1; i++) {
        edge[i] = new ArrayList<Integer>();
        int A = input.nextInt();
        int B = input.nextInt();
        int C = input.nextInt();
        edge[i].add(A);
        edge[i].add(B);
        edge[i].add(C);
    }
    //가중치 세팅
    min[1] = 0;
    for (int i = 2; i < N + 1; i++) {
        min[i] = MAX_VALUE;
    }

    //밸만-포드 알고리즘
    for (int i = 0; i < N - 1; i++) {
        for (int k = 1; k < M + 1; k++) {
            int weight = (int) edge[k].get(2);
            int start = (int) edge[k].get(0);
            int end = (int) edge[k].get(1);
            if (min[start] != MAX_VALUE && min[end] > min[start] + weight) {
                min[end] = min[start] + weight;
            }
        }
    }

    if (findNoCycle(M)) {
        for (int i = 2; i < N + 1; i++) {
            if (min[i] == MAX_VALUE) {
                System.out.println(-1);
            } else {
                System.out.println(min[i]);
            }
        }
    } else {
        System.out.println(-1);
    }
}

//음수 사이클 찾는 알고리즘
private static boolean findNoCycle(int M) {
    for (int i = 1; i < M + 1; i++) {
        int weight = (int) edge[i].get(2);
        int start = (int) edge[i].get(0);
        int end = (int) edge[i].get(1);
        if (min[start] != MAX_VALUE && min[end] > min[start] + weight) {
            return false;
        }
    }
    return true;
}

 

해당 문제를 해결한 풀이 입니다. 출력 초과가 뜨는 경우가 있을 텐데, 이 경우 int 자료형을 long 형으로 바꿔주면 됩니다!

(입력 조건을 확인하고 for 문이 돌아가는 것을 계산해 보면 왜 출력 초과 오류가 뜨는지 알 수 있을 것입니다!)