다익스트라 알고리즘(Dijkstra Algorithm) - JAVA

 

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

그래프에서 여러 개의 노드가 있을 때, 특정한 한 정점(=노드)에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘입니다. 다익스트라 최단 경로 알고리즘은 '음의 간선' 즉, 가중치가 0보다 작은 값이 아닌 경우에 때 정상 동작합니다. 현실 세계에서의 길(간선) 음의 간선으로 표현되지 않아 다익스트라 알고리즘은 실제로 인공위성 GPS 소프트웨어 등에서 가장 많이 사용됩니다.

다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류됩니다. 왜냐하면 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복합니다.

 

 

 

동작과정

1.  출발 노드를 설정
2.  최단 거리 테이블 초기화
3.  방문하지 않은 노드 중에서 최단 거리(가중치)가 가장 짧은 노드 선택
4.  해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5.  위 과정에서 3, 4번 반복

 

최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원의 리스트에 저장하며 리스트를 계속 갱신하는 특징이 있다.  매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인하고, 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 갱신을 합니다. 쉽게 구현하면 매번 최단 거리 테이블을 선형적으로(모든 원소를 앞에서부터) 탐색을 하는 방법이 있지만, 최단 거리가 가장 짧은 노드를 찾기 위해 우선순위 큐 사용하면 단순 탐색보다 시간 복잡도를 줄일 수 있습니다.

 

선형 탐색) 시간 복잡도 O(V²) 에서   -> 우선순위 큐) 시간 복잡도 O(ElogV) 로 줄일 수 있다.

 

 

 

---

 

 

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

백준 1753 최단경로 문제인데 다익스트라를 구현하는 기초 문제입니다. 위에서 배운 내용을 토대로 코드를 구현해보겠습니다.

 

문제에서 주어진 테스트 케이스의 그래프의 형태입니다. 단계별로 풀어내 보도록 하겠습니다.

 

 

1. 먼저 출발 지점의 노드가 1로 주어져 우선순위 큐에 넣습니다. 출발 노드에서 출발 노드로의 거리는 0이니 0으로 초기화가 됐습니다.

노드 번호	1	2	3	4	5
가중치	0	MAXVALUE(=무한)	MAXVALUE(=무한)	MAXVALUE(=무한)	MAXVALUE(=무한)
우선순위 큐	(거리: 0, 노드 1)

 

 

2. 우선순위 큐를 사용하기 때문에 거리가 가장 짧은 노드를 선택하기 위해서는 단순히 큐에서 노드를 꺼내면 됩니다. 해당 노드를 이미 처리한 적이 있으면 무시하고 처리하지 않은 노드에 대해서만 처리하면 됩니다. 1번까지 가는 최단거리가 0이므로, 1번 노드를 거쳐 연결된 2번 3번까지 가는 최소 비용을 계산합니다. => 2(0+2) , 3(0+3) 

 

꺼낸 원소: (거리 0, 노드 1)

노드 번호	1	2	3	4	5
가중치	0	2	3	MAXVALUE(=무한)	MAXVALUE(=무한)
우선순위 큐	(거리: 2, 노드 2), (거리: 3, 노드 3)

 

3. 이어서 다시 우선순위 큐에서 원소를 꺼내서 동일한 과정을 반복합니다.

 

꺼낸 원소: (거리 2, 노드 2)

노드 번호	1	2	3	4	5
가중치	0	2	3	7	MAXVALUE(=무한)
우선순위 큐	(거리: 3, 노드 3) , (거리: 7, 노드 4)

 

4. 3번 노드에서 4번 노드로 가는 가중치가 6이라  ( 3+6 > 7) 이 되어 4번으로 가는 최단 경로는 갱신이 되지 않고 넘어가게 됩니다.

 

꺼낸 원소: (거리 3, 노드 3)

노드 번호	1	2	3	4	5
가중치	0	2	3	7	MAXVALUE(=무한)
우선순위 큐	(거리: 7, 노드 4)

 

5. 해당 노드에서 5번 노드로 가는 길은 없어 큐가 비게 되어 종료가 됩니다.

 

꺼낸 원소: (거리 7, 노드 4)

노드 번호	1	2	3	4	5
가중치	0	2	3	7	MAXVALUE(=무한)
우선순위 큐

 

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[] visit;
    //최단 거리 테이블
    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];
        visit = 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));
        }

        //다익스트라 알고리즘 수행
        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 (!visit[now.v]) {
                visit[now.v] = true;
            }

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

                //방문하지 않았고, 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧을 경우
                if (!visit[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]));
                }
            }
        }
    }
}

 

 

 

 

 

 

 

[참고]

나동빈 - 이코테