[알고리즘] 다익스트라

오늘 시험에 다익스트라가 나온대서 정리하고 넘어가려고 한다.

예전에 최소비용 구하기 풀면서 정리해둔 글이 있어서 풀이를 가져왔다.  https://nkdev.tistory.com/74

[백준/Java] 1916번 : 최소비용 구하기

 

💡가중치가 있는 그래프의 최단 거리를 구할 때는 다익스트라를 사용

 

 

최단 거리를 구할 거면 BFS를 쓰면 되는데 왜 다익스트라를 또 배우는가?

 

일반적인 BFS는 가중치를 고려하지 않는다. 간선 가중치를 고려하지 않으므로 큐에 들어간 모든 노드들의 방문 우선순위는 같다. 그래서 그냥 가까운 순서대로 탐색할 뿐이다. 따라서 간선의 가중치가 모두 동일한 그래프에서 최단 거리를 구할 때 적절한 알고리즘이다.

 

BFS

잠시 BFS가 최단 거리를 구하는 방법을 살펴보면

• 큐(Queue)를 사용하여 탐색
  • 시작 노드를 큐에 넣고 방문 체크
  • 꺼낸 노드의 인접한 노드들을 탐색하여 큐에 추가
  • 방문하지 않은 노드는 이전 노드 거리 +1로 최단 거리 갱신
• 한 번 방문한 노드는 다시 방문하지 않음
  • BFS는 level 순서대로 탐색하기 때문에 가장 먼저 방문한 경로가 항상 최단 거리임

import java.io.*;
import java.util.*;

public class Main {
    static int v, e, start, end;
    static List<List<Integer>> graph;
    static int[] dist;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        v = Integer.parseInt(br.readLine()); // 정점 개수
        e = Integer.parseInt(br.readLine()); // 간선 개수

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

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            graph.get(b).add(a); // 무방향 그래프
        }

        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        System.out.println(bfs(start, end));
    }

    static int bfs(int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        dist = new int[v + 1];
        visited = new boolean[v + 1];

        queue.offer(start);
        visited[start] = true;
        dist[start] = 0; // 시작 노드는 거리 0

        while (!queue.isEmpty()) {
            int now = queue.poll(); // 현재 노드 꺼냄

            for (int next : graph.get(now)) { // 인접 노드 탐색
                if (!visited[next]) { // 아직 방문하지 않은 경우만
                    queue.offer(next);
                    visited[next] = true;
                    dist[next] = dist[now] + 1; // 거리 증가
                }
            }
        }
        return dist[end]; // 최단 거리 반환
    }
}

간선의 가중치가 모두 같아서 큐에서 꺼낸 노드의 인접 노드를 다시 큐에 넣을 때 거리를 1씩 증가시키고 있다. 

그리고 큐에서 노드를 꺼낼 때도 어차피 다음에 어떤 노드를 탐색해도 가중치가 다 똑같이 1씩 증가하니까 그냥 큐에 들어온 순서대로 빼서 다음 탐색할 노드를 정하고 있다.

 

반면 다익스트라는 가중치를 고려한다. 우선순위 큐를 써서 가중치가 가장 작은 노드부터 방문할 수 있고, 이미 최단거리가 확정된 노드는 다시 방문하지 않게 할 수 있다. 그래서 탐색 경로가 효율적이다.

 

가중치가 모두 다른 그래프의 최단거리를 구할 때 BFS를 쓰면 불필요한 경로를 탐색하게 된다. 큐에서 노드를 하나 빼서 다음 탐색 노드를 정할 때 가중치를 전혀 고려하지 않기 때문이다. 가중치가 모두 다를 때는 현재 큐에 들어있는 모든 노드 중 가중치가 최소인 노드부터 먼저 탐색해야 최소 거리 후보들 먼저 탐색할 수 있다.

 

다익스트라

다익스트라가 최단거리를 구하는 방법을 살펴보자.

• 우선순위 큐(PriorityQueue) 사용
  • 시작 노드를 큐에 넣고 최단 거리 테이블(minDist) 초기화
  • 우선순위 큐에서 현재 가장 짧은 거리의 노드를 꺼냄
• 현재 노드와 연결된 노드들 거리 업데이트
  • 현재 노드를 기준으로 인접한 노드까지의 거리(현재 거리 + 가중치) 계산
  • 기존에 저장된 거리보다 작으면 업데이트 후 큐에 추가
• 모든 노드가 처리될 때까지 반복
  • 큐에서 꺼낸 노드의 거리가 기존 최단 거리보다 크면 무시
  • 우선순위 큐에서 poll()하는 노드가 항상 현재까지 확인된 최단 거리이므로, 한 번 확정된 값은 다시 갱신되지 않음

import java.io.*;
import java.util.*;

public class Main {
    static int v, e, start;
    static List<List<Node>> graph;
    static int[] minDist;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        // 정점과 간선 개수 입력
        v = Integer.parseInt(br.readLine());
        e = Integer.parseInt(br.readLine());

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

        // 간선 정보 입력 (양방향 그래프 X, 단방향 그래프)
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Node(b, w));
        }

        start = Integer.parseInt(br.readLine()); // 시작 노드 입력

        // 최단 거리 배열 초기화 (무한대로 설정)
        minDist = new int[v + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[start] = 0; // 시작 노드는 거리 0

        dijkstra(start);
        
        // 결과 출력
        for (int i = 1; i <= v; i++) {
            System.out.println("Node " + i + " : " + (minDist[i] == Integer.MAX_VALUE ? "INF" : minDist[i]));
        }
    }

    static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0)); // 시작 노드를 큐에 삽입

        while (!pq.isEmpty()) {
            Node now = pq.poll(); // 현재 가장 짧은 거리의 노드를 꺼냄
            if (now.weight > minDist[now.num]) continue; // 이미 확정된 최단 거리보다 크면 무시

            // 현재 노드의 인접 노드 탐색
            for (Node next : graph.get(now.num)) {
                int newWeight = minDist[now.num] + next.weight;
                if (newWeight < minDist[next.num]) { // 더 짧은 거리 발견 시 갱신
                    minDist[next.num] = newWeight;
                    pq.offer(new Node(next.num, newWeight)); // 우선순위 큐에 삽입
                }
            }
        }
    }
}

// 우선순위 큐를 위한 Node 클래스
class Node implements Comparable<Node> {
    int num, weight;
    
    Node(int num, int weight) {
        this.num = num;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight; // 거리가 짧은 순으로 정렬
    }
}

if(minDist[next.num] > minDist[now.num]+next.weight){
	minDist[next.num] = minDist[now.num]+next.weight
}

 

이 부분이 최소비용을 갱신하는 부분이다.

• minDist
  • 시작 노드로부터의 최소 거리가 저장되는 곳
  • 초기값은 모두 무한대
  • 여기에 시작 노드부터 BFS 탐색해나가며 만난 각 노드들의 시작 노드로부터의 최소 거리를 계속해서 업데이트시킴
• now
  • 현재 노드
  • 지금 탐색할 모든 노드 중 비용이 가장 최소인 노드
• next
  • 현재 노드의 인접 노드
• minDist[next.num] > minDist[now.num]+next.weight
  • '현재까지 발견된 시작 노드에서 next로의 최소 비용 > 현재까지 발견된 시작 노드에서 현재 노드로의 최소 비용 + 현재 노드에서 next로 가는 비용'
  • 즉 시작 노드에서 next로 갈 때 현재 노드(now)를 거쳐서 가는 게 효율적인지 거치지 않는 게 효율적인지 비교해서 더 작은 값을 업데이트하는 작업이다. 

다익스트라는 방문 체크를 안 해도 될까?

BFS는 모든 노드를 한 번씩만 방문한다. 같은 노드를 여러 번 방문하지 않기 위해 큐에 들어간 노드는 방문 체크가 필요하다.

 

다익스트라는 minDist가 방문 체크 역할을 한다. 더 짧은 거리로 갱신되었을 때만 큐에 삽입하고 있고, 이미 더 짧은 거리로 방문한 적이 있으면 큐에서 꺼내도 continue로 무시된다. 또한 더 짧은 경로를 찾기 위해 이미 방문한 노드도 다시 확인해야할 수 있기 때문에 방문 체크를 하면 안 된다.

 

다익스트라는 음의 간선이 존재하면 안 된다

다익스트라는 한 번 꺼낸 정점은 확정된 것이라고 생각하고 재처리하지 않는다.

그런데 이미 확정한 정점이 더 짧은 경로로 다시 갱신되어야 하는 상황이 발생하면 그 후의 최단 경로 계산이 다 망가지기 때문이다.

 

다익스트라는 간선이 아니라 '정점+누적 비용'을 우선순위 큐에 넣고 꺼낸다. 그리고 꺼낸 노드와 연결된 간선을 따라 이웃 정점까지의 거리를 그리디하게 갱신해나간다. 그런데 이 때 뒤늦게 음의 간선을 발견했다면 최단 경로라고 확신했던 정점이 최단 경로가 아니게 된다.

 

만약 A->B 비용이 4

A->C 비용이 1

C->B 비용이 -2

라고 했을 때 

 

시작점이 A라면 큐에서 A를 꺼낸다. 

A->B(4) -> dist[B] = 4

A->C(1) -> dis[C] = 1

큐 상태 : (1, C) (4, B) 오름차순정렬됨

 

큐에서 C를 꺼낸다.

C->B(-2) -> dist[B] = min(1-2, 4) = -1 갱신됨

큐에 추가 : (-1, B)

 

여기서 B는 (4, B)로 이미 큐에 들어있는데 더 짧은 비용(-1, B)으로 다시 큐에 들어갔다.

그리고 큐에서 다시 오름차순으로 노드를 빼면 (-1, B)가 나온다.

 

그리고 마지막으로 큐에 남아있던 (4, B)를 꺼내는데 이 값은 dist[B] 즉 -1보다 크기 때문에 무시된다.

백준 1916번 최소비용 구하기

다익스트라를 이 문제에 적용하면 num(도시 번호), weight(가중치) 변수를 가진 Node 클래스를 만들어서 

compareTo로 weight가 작은 순서대로 우선 순위 큐에 정렬시키고 weight 작은 곳부터 방문하게 한다. 

그리고 탐색 중 임의의 노드 K에 도착했을 때 이전에 구했던 경로의 가중치 합보다 현재 경로의 가중치 합이 더 크다면 더이상 탐색하지 않도록 무시하게 한다.

 

1️⃣ 인접 리스트로 간선 정보 입력하기

인접 행렬을 사용하면 같은 노드 사이 간선이 두 개 존재할 때 간선 가중치가 덮어씌워질 수 있다.

예) 

1 2 5

1 2 3

 

따라서 인접 리스트 List<List<Node>>를 사용한다.

 

2️⃣ BFS+우선순위큐로 A->B 경로의 최소 간선 비용 구하기

1에서부터 출발해 각 노드에 도착할 때 최소 비용을 저장할 배열은 다음과 같다. 

초기값을 무한대로 설정해둔 이유는 더 작은 비용이 구해질 때마다 업데이트하기 위해서이다.

1	2	3	4	5
0	무한대	무한대	무한대	무한대

출발지인 1부터 시작. 1에서 갈 수 있는 노드는 2, 3, 4, 5이므로 비용을 업데이트해준다. (빨간색으로 표시)

그리고 1에서 갈 수 있는 노드를 모두 방문했으므로 방문 체크해준다. (초록색으로 표시)

1	2	3	4	5
0	2	3	1	10

아직 방문하지 않은 노드 중 비용이 가장 작은 노드는 4이므로 다음 탐색 노드는 4이다.

노드 4에서 갈 수 있는 노드는 5 하나이다.

기존 비용 10 VS 1에서 4를 거쳐 5로 갈 때의 비용은 1+3=4 둘을 비교하면 4가 더 작으므로 10을 4으로 업데이트한다.

그리고 4도 방문 체크해준다.

1	2	3	4	5
0	2	3	1	4

 

...

 

이런 식으로 나머지 노드들도 방문을 마치고 나면

인덱스 5에 있는 값이 1->5로 가는 데 드는 비용의 최소값이 된다.

 

자바 코드 :

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, A, B, minWeight;
    static List<List<Node>> list;
    static int[] ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        list = new ArrayList<>();
        for(int i=0; i<=N; i++){
            list.add(new ArrayList<>());
        }
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int c1 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list.get(c1).add(new Node(c2, w));
        }

        st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        minWeight = Integer.MAX_VALUE;
        ans = new int[N+1];
        Arrays.fill(ans, Integer.MAX_VALUE);
        ans[A] = 0;

        dijkstra(A);
        System.out.println(ans[B]);
    }

    static void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while(!pq.isEmpty()){
            Node now = pq.poll(); //큐에서 한 개 꺼내기
            if(now.weight > ans[now.num]) continue; //기존 최단 거리보다 크면 무시

            for(Node next: list.get(now.num)){ //now와 인접한 노드들
                int newWeight = next.weight + ans[now.num];
                if(newWeight < ans[next.num]){
                    ans[next.num] = newWeight;
                    pq.offer(new Node(next.num, newWeight));
                }

            }

        }
    }
}

class Node implements Comparable<Node>{
    int num, weight;
    Node(int num, int weight){
        this.num = num;
        this.weight = weight;
    }
    @Override
    public int compareTo(Node o){
        return this.weight - o.weight;
    }
}

파이썬 코드 :

import sys, heapq

# n개의 노드, m개의 간선
# a에서 b까지 가는 데 드는 최소 비용 찾기

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = [[] for i in range(n+1)]

for _ in range(m):
    a, b, w = map(int, sys.stdin.readline().split())
    graph[a].append((w, b))

s, e = map(int, sys.stdin.readline().split())

min_dist = [sys.maxsize]*(n+1)
min_dist[s] = 0

# 큐에 시작 노드를 넣음
# (가중치, 노드 번호)
que = []
heapq.heappush(que, (0, s))

while que:
    now_dist, now_num = heapq.heappop(que)

    if min_dist[now_num] < now_dist:
        continue

    # 지금까지 발견된 next까지의 최단 거리 vs 현재 노드를 거쳐서 next까지 가는 거리 둘 중 작은 값을 min_dist[next]값으로 갱신
    for next_dist, next_num in graph[now_num]:
        new_dist = min_dist[now_num] + next_dist
        if min_dist[next_num] > new_dist:
            min_dist[next_num] = new_dist
            heapq.heappush(que, (new_dist, next_num))

print(min_dist[e])