[알고리즘] 최단 경로 구하기 - 2. 벨만 - 포드

|  벨만-포드

- 가중치가 양수만 있을 때에 다익스트라를 사용했다면,

- 가중치에 음수가 있을 때엔 벨만-포드를 사용한다.

- 기능 : 특정 출발 노드에서 도착 노드까지의 최단 경로 탐색

- 특징 : 가중치 음수 OK,  음수 사이클 여부 판단

- 시간 복잡도 : O(VE)

 

|  벨만-포드 구현하기

- 지난번에 구현했던 다익스트라의 우선순위 큐 버전으로 쓰면 음수도 커버가 가능한데

- 벨만-포드를 사용하게 되면 음수 사이클 여부까지 커버할 수 있다.

- 구현의 순서

1	에지 배열 & 최단 경로 dp 배열 초기화
2	모든 에지를 하나씩 확인하여 최단 경로 업데이트
3	음수 사이클 여부 확인

 

[1] 에지 배열(또는 리스트) & 최단 경로 dp 배열 초기화

- 이 부분은 다익스트라의 노드 클래스가 간선 클래스로 바뀐 것 밖에 없다.

- Edge라는 클래스안에 출발지점, 도착지점, 가중치를 넣어 배열에 저장한다.(또는 리스트에 저장)

edge	1	2	3	4	5
출발
종료
가중

- 최단 경로 dp 배열

dp	1	2	3	4	5
최단

class Edge{
    int from;
    int to;
    int weight;
    
    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}

public void Bellmanford(int v, int e, int[][] data, int start){
    // 1. 간선 정보 및 최단 경로 배열 초기화
    // 1-1. 간선 정보를 배열로 저장
    Edge[] edge = new Edge[e];
    for (int i = 0; i < edge.length; i++) {
        edge[i] = new Edge(data[i][0], data[i][1], data[i][2]);
    }

    // 1-2. 최단 경로 배열
    int[] distDP = new int[v + 1];
    for (int i = 1; i < v + 1; i++) {
        distDP[i] = Integer.MAX_VALUE;
    }
    distDP[start] = 0;
}

 

[2] 모든 에지를 하나씩 확인하여 최단 경로 업데이트

* D는 dp, S는 출발노드, e는 도착노드
D[s] != ∞ 이며, D[e] > D[s] + w 일 때, D[e] = D[s] + w

- 음수 사이클이 없을 때 최대 에지 사용 횟수는 V - 1이다.

* 만약 노드의 개수가 5개이고, 음수사이클이 없다면 아래와 같이 4번 반복하여 최단거리를 확인한다.

dp	1	2	3	4	5
초기	0	∞	∞	∞	∞
1
2
3
4

// 2. 모든 간선을 확인해 정답 배열 업데이트 하기
for (int i = 1; i < v + 1; i++) { // 간선 횟수 + 1만큼 (음수사이클 확인)
    for (int j = 0; j < e; j++) { // 각 간선에 대하여
        Edge cur = edge[j]; 

        if (distDP[cur.from] == Integer.MAX_VALUE) { // 초기화되지x간선 무시(간선X)
            continue;
        }

        // 기존 거리 > 새로운 거리 : 현재 출발지 + 가중치  
        if (distDP[cur.to] > distDP[cur.from] + cur.weight) {
            distDP[cur.to] = distDP[cur.from] + cur.weight;
        }
    }
}

 

[3] 음수 사이클 여부 확인

- 만약에 음수 사이클이 없다면, 최대 에지 사용 횟수는 V 이상이다.

- 바깥 if문 안으로 들어오는 경우가 v번째이상인 경우는 음수사이클이 발생하므로 아래와 같이 작성해주면 완료된다.

if (distDP[cur.to] > distDP[cur.from] + cur.weight) {
    distDP[cur.to] = distDP[cur.from] + cur.weight;

    // 3. 음수 사이클 유무 확인하기
    if (i == v) {
        isMinusCycle = true;
    }
}

* 최종 코드 

public void bellmanFord(int v, int e, int[][] data, int start) {
    // 1. 간선 정보 및 최단 경로 배열 초기화
    // 1-1. 간선 정보를 배열로 저장
    Edge[] edge = new Edge[e];
    for (int i = 0; i < edge.length; i++) {
        edge[i] = new Edge(data[i][0], data[i][1], data[i][2]);
    }

    // 1-2. 최단 경로 배열
    int[] distDP = new int[v + 1];
    for (int i = 1; i < v + 1; i++) {
        distDP[i] = Integer.MAX_VALUE;
    }
    distDP[start] = 0;


    boolean isMinusCycle = false;
    // 2. 모든 간선을 확인해 정답 배열 업데이트 하기
    for (int i = 0; i < v + 1; i++) {
        for (int j = 0; j < e; j++) {
            Edge cur = edge[j];

            if (distDP[cur.from] == Integer.MAX_VALUE) {
                continue;
            }

            if (distDP[cur.to] > distDP[cur.from] + cur.weight) {
                distDP[cur.to] = distDP[cur.from] + cur.weight;

                // 3. 음수 사이클 유무 확인하기
                if (i == v) {
                    isMinusCycle = true;
                }
            }

        }
    }

    System.out.println("음수 사이클 발생 : " + isMinusCycle);
    for (int i = 1; i < v + 1; i++) {
        if (distDP[i] == Integer.MAX_VALUE) {
            System.out.print("INF" + " ");
        } else {
            System.out.print(distDP[i] + " ");
        }
    }
    System.out.println();

}

 

|  백준문제풀기

11657	타임머신
1219	세일즈맨

 

 

 

[ 출처 및 참조 ]

부트캠프 수업 내용 정리

 doit 알고리즘 코딩 테스트 책