[알고리즘] 다익스트라 (Dijkstra) 알고리즘

다익스트라 알고리즘이란 ?

• 그래프의 최단 경로를 구하는 알고리즘

• 하나의 정점에서 출발하는 최단 거리를 구함. (출발지만 정한 상태에서)

• 음수 가중치 없어야 함.

• 인접 행렬로 표현한 그래프의 시간복잡도 : O(N^2)

• 우선순위 큐 사용하면 O(MlogN) 까지 낮출 수 있음.

• 그리디, DP 사용

원리

기본적으로 두 단계를 반복한다.

1. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 (그리디)
2. 해당 노드로부터 갈 수 있는 노드들의 비용 갱신 (DP)

백준 최단경로 문제

코드

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

public class Main {

    static class Node{
        int v; // 노드 번호
        int cost; // 가중치

        public Node(int v, int cost) {
            this.v = v;
            this.cost = cost;
        }
    }

    // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
    static ArrayList<Node>[] graph;
    
    // 방문한 적이 있는지 체크하는 목적의 리스트
    static boolean[] visited;
    
    // 최단 거리 배열
    static int[] dist;

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

        int v = Integer.parseInt(st.nextToken()); // 정점 개수
        int e = Integer.parseInt(st.nextToken()); // 간선 개수
        int k = Integer.parseInt(br.readLine()); // 시작 정점 번호

        graph = new ArrayList[v + 1];
        dist = new int[v + 1];
        visited = new boolean[v + 1];
		
        // 초기화 과정
        for (int i = 1; i <= v; i++) {
            graph[i] = new ArrayList<>();
            dist[i] = Integer.MAX_VALUE; // 최대값으로 초기화 (최단거리를 찾기 위함)
        }

		// 그래프 간선 연결 
        for (int i = 0; i < e; i++) {
            // u -> v 로 가는 가중치 w가 주어진다.
            st = new StringTokenizer(br.readLine());
            int inputU = Integer.parseInt(st.nextToken());
            int inputV = Integer.parseInt(st.nextToken());
            int inputW = Integer.parseInt(st.nextToken());

            graph[inputU].add(new Node(inputV, inputW));
        }

        // k 정점부터 다익스트라 알고리즘 수행
        dijkstra(k);

        for (int i = 1; i <= v; i++) {
            System.out.println(dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]);
        }
    }

    static void dijkstra(int start) {
        // 우선 순위 큐 사용, 가중치를 기준으로 오름차순
        PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        
        // 시작 노드에 대해서 초기화
        q.add(new Node(start, 0));
        dist[start] = 0;

        while (!q.isEmpty()) {
            // 현재 최단 거리가 가장 짧은 노드를 꺼내서 방문 처리
            Node now = q.poll();

            if (!visited[now.v]) {
                visited[now.v] = true;
            }

            for (Node next : graph[now.v]) {

                // 방문하지 않았고, 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧을 경우 갱신, 큐에 노드 넣어주기 
                if (!visited[next.v] && dist[next.v] > now.cost + next.cost) {
                    dist[next.v] = now.cost + next.cost;
                    q.add(new Node(next.v, dist[next.v]));
                }
            }
        }
    }
}