hyeoneee's blog

두번째로 벨만포드를 정리해보고자 한다.

음수 가중치가 있을때 최단거리를 구하는 알고리즘이다.

V번 E개의 간선에 대해 dist 배열 갱신한다.
* V번째에 dist 배열의 갱신이 발생하면 -> 음의 사이클 존재

요 음의 사이클이 존재 하는지 안하는지가 벨만포드에서 가장 중요하다.

이유는? (V-1)번까지 돌았는데 V번째에서 dist 배열 갱신이 발생한다면?

사이클이 있는데 그값이 계속 감소한다는 것이다. 가중치가 음수가 있기 때문에 가능한 현상이다.

그래서 문제를 풀다보면 음의 사이클이 있는가? 를 묻는 문제도 더러 있다

샘플코드 

    static int[] dist;
    static int N;
    static ArrayList<Node>[] adj = new ArrayList[N+1];
    static int belman() {
        //1. dist 배열 INF 값으로 채우기, 출발지는 0으로
        Arrays.fill(dist, INF);
        dist[1] = 0;

        //2. V번 E개의 간선은 탐색 (음수 사이클 체크를 위해 V-1+1번 체크)
        boolean isUpdated;
        for (int i = 1; i <= N; i++) { // V
            isUpdated = false;
            for (int here = 1; i <= N; here++) {// E
                for (Node next : adj[here]) {//dist 배열 업데이트
                    int nextCost = dist[here] + next.cost;
                    if (dist[here] != INF && dist[next.idx] > nextCost) {
                        //dist[here] != INF : 연결이 안된다는 것을 확인 , 현재노드인 here가 이전에 방문했어야함 그래야 거쳐서 가니깐 
                        dist[next.idx] = nextCost;
                        isUpdated = true;
                    }
                }
                if (!isUpdated) break; // 더 이상 최단 경로 갱신이 안일어 나면 조기종료
            }
            if (isUpdated) return -1;
        }
        return dist[N];
    }