코딩테스트/알고리즘

10. 그래프 - 최단 경로 알고리즘(다익스트라, 플로이드 워셜)

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

개념

  • 정의: 그래프 구조에서 가장 짧은 경로를 찾는 알고리즘

 

다익스트라 알고리즘

개념

  • 정의: 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하는 알고리즘
    • 최종적으로 각 노드까지의 최단 거리 정보가 저장
  • 시간 복잡도: O(ElogV) : E - 간선 개수, V - 노드 개수
  • 특징: 
    • 그리디 알고리즘: 매 상황에서 방문하지 않는 가장 비용이 적은 노드를 선택하여 반복
    • 한 번 처리(방문)된 노드의 최단 거리는 고정
    • 결과 각 노드까지의 최단 거리 정보가 저장
  • 동작과정 간단 요약
    1. 출발 노드 설정 & 최단 거리 테이블 초기화
    2. 아래 과정 반복
      • 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택
      • 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신

 

진행 흐름

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
public static int n, m, start;

1. 가중치 그래프 정보 입력받기

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

ArrayList<ArrayList<Node>> graph = new ArrayList<>();
for(int i=0; i<=10; i++){
    graph.add(new ArrayList<>());
}

// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph.get(a).add(new Node(b, c));
}

 

 

2. 최단 거리 테이블 & 우선순위 큐 준비

  • 최단 거리 테이블: i번째 노드의 최단 거리 정보를 저장하는 것
    • 주의! - 최단 거리 초기화 할때 Integer.MAX_VALUE를 사용하면 오버플로우 때문에 결과가 이상하게 발생 가능
  • 우선순위 큐: 단계마다 최단 거리가 가장 짧은 노드를 선택하기 위해 사용
  • 우선순위큐에 들어가는 Node의 의미는 가중치 그래프의 Node와 다름
    • 우선순위큐: i번째 노드의 최단거리가 d라는 의미
    • 가중치 그래프: 다음 노드 i로 가는 가중치가 d라는 의미

-> 큐에 있는 최단거리 정보와 최단 거리 테이블의 정보를 비교해서 계속 업데이트 해나가는 과정

//최단 거리 테이블 - 거리 무한대로 초기화
int[] d = new int[n+1];
Arrays.fill(d, MAX);

//우선순위큐: 거리가 작을수록 우선순위가 높도록 설정(오름차순)
PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> n1.d - n2.d);

 

 

3. 시작 노드 초기화

  • 최단 거리 테이블 거리 0으로 설정
  • 우선순위 큐에 삽입 (start노드 최단 거리 0)

코드

d[start] = 0;
pq.offer(new Node(start, 0));

 

작동 방식

 

 

4. 반복문을 통한 최단 거리 테이블 갱신

  1. 우선순위 큐에서 거리가 가장 짧은 노드를 현재 노드로 설정
    • 단, 현재 노드가 이미 방문한 노드면 continue
    • = 현재 노드에 저장된 최단 거리 정보가 최단 거리 테이블 보다 작다면 이미 이전에 업데이트 된 것
  2. 그래프 구조를 통해 현재 노드와 연결된 노드 확인
  3. 아래 2개의 값 비교하여 갱신 여부 확인
    • 현재 노드의 최단 거리 값 + 간선 가중치
    • 다음 노드의 최단 거리 값
  4. if 갱신이 되었다면, 우선순위 큐에 삽입

코드

//4. 우선순위 큐가 빌때까지 반복
while(!pq.isEmpty()){
    Node now = pq.poll();
    //현재 큐에 있는 최단 거리 정보가 최단 거리 테이블에 있는 값보다 크면 볼 필요가 없음
    if(d[now.i] < now.d) continue;

    for(Node next : graph.get(now.i)){
        // 현재 노드 최단 거리 값 + 다음 노드 간선 가중치
        // 다음 노드의 최단 거리 값
        int cost = d[now.i] + next.d;

        //현재 노드의 최단 거리 값 + 다음 노드 가중치가 더 작다면
        if(d[next.i] > cost){
            //최단 거리 테이블 업데이트 및 최단 거리 정보 큐에 삽입
            d[next.i] = cost;
            pq.offer(new Node(next.i, cost));
        }
    }
}

 

 

작동 방식

노드 3번이 이미 우선순위 큐에 있었지만, 최단 거리 테이블이 갱신되었기에 다시 우선순위 큐에 삽입

(어차피 중복 삽입이 되어도 방문 처리를 하기 때문에 상관x)

 

 

전체 코드

static final int MAX = 999;

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

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

    ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    for(int i=0; i<=10; i++){
        graph.add(new ArrayList<>());
    }

    // 모든 간선 정보를 입력받기
    for (int i = 0; i < m; i++) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
        graph.get(a).add(new Node(b, c));
    }

    //1. 최단 거리 테이블 & 우선순위 큐 준비
    int[] d = new int[n+1];
    Arrays.fill(d, MAX);

    PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> n1.d - n2.d);

    //3. 시작 노드 초기화
    pq.offer(new Node(start,0));
    d[start] = 0;

    //4. 우선순위 큐가 빌때까지 반복
    while(!pq.isEmpty()){
        Node now = pq.poll();
        //현재 큐에 있는 최단 거리 정보가 최단 거리 테이블에 있는 값보다 크면 볼 필요가 없음
        if(d[now.i] < now.d) continue;

        for(Node next : graph.get(now.i)){
            // 현재 노드 최단 거리 값 + 다음 노드 간선 가중치
            // 다음 노드의 최단 거리 값
            int cost = d[now.i] + next.d;

            //현재 노드의 최단 거리 값 + 다음 노드 가중치가 더 작다면
            if(d[next.i] > cost){
                //최단 거리 테이블 업데이트 및 최단 거리 정보 큐에 삽입
                d[next.i] = cost;
                pq.offer(new Node(next.i, cost));
            }
        }
    }

    System.out.println(Arrays.toString(d));

}

static class Node{
    int i;
    int d;

    public Node(int i, int d){
        this.d = d;
        this.i = i;
    }
}

 

플로이드 워셜 알고리즘

개념

  • 정의: 모든 노드에서 다른 모든 노드까지 최단 경로를 모두 계산하는 알고리즘
  • 시간복잡도: O(V^3)
    • 시간복잡도가 높기 떄문에 노드 개수가 작을때만 사용 가능
  • 동작과정 간단 요약
    • 점화식 사용: a->b 의 거리 vs a -> k -> b의 거리 중에 더 짧은 것을 선택하는 구조
    • D<ab> = min( D<ab>, D<ak> + D<kb> )

 

구현 방법

// 노드의 개수(N), 간선의 개수(M)
public static int n, m;

 

최단 거리 테이블

  • 2차원 리스트 형태로 최단 거리 테이블을 작성
    • 2차원 리스트에 간선 정보가 다 포함 되어 있으므로, 굳이 가중치 그래프 구조는 필요x
// 2차원 배열(그래프 표현)를 만들기
public static int[][] d = new int[n+1][n+1];

 

진행 흐름

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

  • 초기 간선 정보를 가지고 최단 거리 테이블 초기화
    • 자기 노드 비용 - 0으로 설정
    • 다른 노드 비용 - 간선 가중치
    • 연결이 없다면 - 무한으로 설정

코드

// 3. 초기값 무한으로 설정
for (int i = 0; i < n; i++) {
    Arrays.fill(d[i], Integer.MAX_VALUE);
}

// 1. 자기 노드 비용 - 0으로 설정
for (int a = 1; a <= n; a++) {
    d[a][a] = 0;
}

// 2. 다른 노드 비용 - 간선 가중치
// 간선 개수 만큼 반복
for (int i = 0; i < m; i++) { 
    // A에서 B로 가는 비용은 C라고 설정
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    d[a][b] = c;
}

 

작동 방식

 

2. 반복문을 통한 최단 거리 테이블 갱신

  • 삼중 반복문을 통해 하나씩 k번 노드를 거쳐 가는 경우를 고려해 테이블 갱신
  • 예시) k = 1
    • 2->3 거리 = 2-> 3거리 vs 2-> 1 -> 3거리 비교

코드

// 점화식에 따라 플로이드 워셜 알고리즘을 수행
for (int k = 1; k <= n; k++) {
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            d[a][b] = Math.min(d[a][b], d[a][k] + d[k][b]);
        }
    }
}

 

작동 방식

k가 1일 때