코딩테스트/알고리즘

10-2. 그래프 - 음수 간선의 최단 거리 - 벨만 포드 알고리즘

초코chip 2024. 4. 2. 20:26

개념

최단 거리 문제 종류

  • 모든 간선이 양수인 경우 - 다익스트라 알고리즘
  • 음수 간선이 있는 경우 - 벨만 포드 알고리즘
    • 음수 간선 순환이 없는 경우 - 다익스트라 O
    • 음수 간선 순환이 있는 경우 - 다익스트라 X

 

벨만 포드 알고리즘

  • 시간 복잡도: O(VE)  - 다익스트라 알고리즘에 비해 느림
  • 동작과정 간단 요약
    • 출발 노드 설정 & 최단 거리 테이블 초기화
    • 아래 과정을 N-1번 반복
      • 전체 간선 E개를 하나씩 확인 ( 다익스트라는 특정 노드에 붙어있는 간선만 확인함 )
      • 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
    • 만약, 음수 간선 순환이 발생하는지 체크하고 싶다면, N-1 반복을 다시 한 번 더 수행
      • 이때, 최단 거리 테이블이 갱신된다면 음수 간선이 존재하는 것

 

vs 다익스트라 알고리즘

  • 다익스트라 알고리즘
    • 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
    • 음수 간선이 없다면 최적 해 찾기 가능
  • 벨만 포드 알고리즘
    • 매번 모든 간선을 전부 확인
      • 따라서 다익스트라의 알고리즘에서의 최적 해를 항상 포함
    • 다익스트라의 알고리즘에 비해 시간이 오래 걸리지만 음수 간선 탐지 가능

 

 

코드

1. 가중치 그래프 생성

간선 관점으로 가중치 그래프 입력

//1. 가중치 그래프 생성
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int m = sc.nextInt();
int start = sc.nextInt();

ArrayList<Edge> edges = new ArrayList<>();

// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();

    edges.add(new Edge(a,b,c));
}

 

2. 최단 거리 테이블 초기화

//2. 최단 거리 테이블
int[] d = new int[n+1];
Arrays.fill(d, MAX);

 

3. 반복문처리 진행

노드 개수 V-1번 만큼 전체 간선을 확인

  • 전체 간선 E개를 하나씩 확인 ( 다익스트라는 특정 노드에 붙어있는 간선만 확인함 )
  • 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
//V-1 만큼 반복
for(int i=1; i< n; i++){
    //모든 간선 확인
    for(Edge e : edges){
        //현재 노드 최단 거리 비용 + 간선 비용 vs 다음 노드 최단 거리 비용
        if(d[e.e] > d[e.s] + e.w){
            d[e.e] = d[e.s] + e.w;
        }
    }
}

 

 

4. 음의 사이클 존재 확인

마지막으로 최단 거리 테이블을 확인했을 때, 갱신된다면 음의 사이클이 존재하는 것

//4. 음의 사이클 존재 여부 확인 - 한번이라도 갱신되면 음의 사이클이 존재하는 것
boolean hasCycle = false;
for (Edge e : edges) {
    if (d[e.s] != MAX && d[e.s] + e.w < d[e.e]) {
        hasCycle = true;
        break;
    }
}

 

 

5. 결과 확인

//5. 결과 확인: 최단 거리 테이블 출력
if (hasCycle) {
    System.out.println("Graph contains a negative weight cycle");
} else {
    // 결과 확인: 최단 거리 테이블 출력
    for (int i = 1; i <= n; i++) {
        if (d[i] == MAX)
            System.out.print("Infinity ");
        else
            System.out.print(d[i] + " ");
    }
}

 

 

 

전체 코드

public class struct {
    static final int MAX = 999;

    public static void main(String[] args) throws IOException {
        //1. 가중치 그래프 생성
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int start = sc.nextInt();

        ArrayList<Edge> edges = new ArrayList<>();

        // 모든 간선 정보를 입력받기
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            edges.add(new Edge(a,b,c));
        }


        //2. 최단 거리 테이블
        int[] d = new int[n+1];
        Arrays.fill(d, MAX);

        //3. 시작 노드 초기화
        d[start] = 0;

        //4.정점 개수 - 1 만큼 반복
        for(int i=1; i< n; i++){
            //모든 간선 확인
            for(Edge e : edges){
                //현재 노드 최단 거리 비용 + 간선 비용 vs 다음 노드 최단 거리 비용
                if(d[e.e] > d[e.s] + e.w){
                    d[e.e] = d[e.s] + e.w;
                }
            }
        }

        //5. 음의 사이클 존재 여부 확인 - 한번이라도 갱신되면 음의 사이클이 존재하는 것
        boolean hasCycle = false;
        for (Edge e : edges) {
            if (d[e.s] + e.w < d[e.e]) {
                hasCycle = true;
                break;
            }
        }

        //6. 결과 확인: 최단 거리 테이블 출력
        if (hasCycle) {
            System.out.println("Graph contains a negative weight cycle");
        } else {
            // 결과 확인: 최단 거리 테이블 출력
            for (int i = 1; i <= n; i++) {
                if (d[i] == MAX)
                    System.out.print("Infinity ");
                else
                    System.out.print(d[i] + " ");
            }
        }

    }

    static class Edge{
        int s;
        int e;
        int w;

        public Edge(int s, int e, int w){
            this.s=s;
            this.e = e;
            this.w = w;
        }
    }
}