다익스트라 알고리즘(Dijkstra's Algorithm)은 단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 최단 경로 알고리즘 중 하나입니다. 이 알고리즘은 음의 가중치를 갖는 간선이 없는 그래프에서 사용됩니다. 다익스트라 알고리즘은 주로 두 정점 사이의 최단 경로를 찾을 때 사용되며, 네트워크 라우팅 등 다양한 분야에서 활용됩니다.

다익스트라 알고리즘의 동작

1. 출발 노드 선택: 출발 노드를 선택하고 해당 노드로부터의 거리를 0으로 설정합니다.

2. 거리 갱신: 출발 노드와 직접 연결된 모든 노드까지의 거리를 계산하고, 현재까지의 최단 거리로 갱신합니다.

3. 최단 거리 노드 선택: 아직 처리하지 않은 노드들 중에서 최단 거리를 갖는 노드를 선택합니다.

4. 선택한 노드를 통해 갱신: 선택한 노드를 통해 갈 수 있는 다른 노드들까지의 거리를 계산하고, 현재까지의 최단 거리로 갱신합니다.

5. 모든 노드에 대해 반복: 위의 과정을 모든 노드에 대해 반복하면서 최단 거리를 계산합니다.

최단 경로 업데이트 메모리에 Integer.MAX_VALUE로 초기화 합니다.

시작 지점부터 각 인접한 노드 까지의 거리를 업데이트 합니다.

거리가 가장 짧은 노드인 B를 선택하여 각 인접한 노드까지의 거리를 업데이트 합니다. 이 때 이미 값이 있다면 원래의 값과 비교하여 더 작은 값으로 업데이트 합니다.

위 방법을 반복하여 시작 지점 부터 각 노드까지의 총 거리를 구할 수 있습니다.

다익스트라 시간복잡도

다익스트라 알고리즘은 시간복잡도가 O(V^2)이지만, 우선순위 큐를 이용하여 최소 거리 노드를 빠르게 선택하는 경우에는 O(ElogV)로 개선될 수 있습니다.

V : 노드 수, E : 간선 수

다익스트라 예시

// 다익스트라 기본 구현


import java.util.ArrayList;

public class Main {

	// Node 클래스: 그래프의 노드를 나타내는 클래스
	// to: 노드까지의 도착지점, weight: 해당 노드까지의 가중치
    static class Node{
        int to;
        int weight;

        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

	// dijkstra 메서드: 다익스트라 알고리즘을 구현한 메서드
	// v: 그래프의 노드 수, data: 그래프의 연결 정보를 저장한 배열, start: 출발 노드
    public static void dijkstra(int v, int[][] data, int start) {
        ArrayList<ArrayList<Node>> graph = new ArrayList<>(); // 우선 그래프를 ArrayList<ArrayList<Node>> 형태로 생성하고, 연결 정보를 저장
        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < data.length; i++) {
            graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
        }

        int[] dist = new int[v + 1]; // dist 배열은 출발 노드에서 각 노드까지의 최단 거리를 저장, 초기값은 무한대로 설정

        for (int i = 1; i < v + 1; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        dist[start] = 0;

        boolean[] visited = new boolean[v + 1]; // visited 배열은 방문한 노드를 표시하기 위한 배열

		// 반복문을 통해 각 노드까지의 최단 거리를 계산하고, dist 배열을 업데이트합니다.
        for (int i = 0; i < v; i++) {
            int minDist = Integer.MAX_VALUE;
            int curIdx = 0;
            for (int j = 1; j < v + 1; j++) {
                if(!visited[j] && dist[j] < minDist){
                    minDist = dist[j];
                    curIdx = j;
                }
            }

            visited[curIdx] = true;

            for (int j = 0; j < graph.get(curIdx).size(); j++) {
                Node adjNode = graph.get(curIdx).get(j);
                if(dist[adjNode.to] > dist[curIdx] + adjNode.weight){
                    dist[adjNode.to] = dist[curIdx] + adjNode.weight;
                }
            }
        }

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

    public static void main(String[] args) {
        int[][] data = {{1, 2, 2}, {1, 3, 3}, {2, 3, 4}, {2, 4, 5}, {3, 4, 6}, {5, 1, 1}};
        dijkstra(5, data, 1);
    }
}

// 다익스트라 우선순위 큐 사용


import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main2 {

    static class Node{
        int to;
        int weight;

        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

	// dijkstra 메서드: 우선순위 큐를 사용한 다익스트라 알고리즘을 구현한 메서드
	// v: 그래프의 노드 수, data: 그래프의 연결 정보를 저장한 배열, start: 출발 노드
    public static void dijkstra(int v, int[][] data, int start) {
        ArrayList<ArrayList<Node>> graph = new ArrayList<>();
        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < data.length; i++) {
            graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
        }

        int[] dist = new int[v + 1];

        for (int i = 1; i < v + 1; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        pq.offer(new Node(start, 0)); // 출발 노드부터 우선순위 큐에 넣어줌. (노드의 weight를 기준으로 오름차순으로 정렬)

		// 우선순위 큐가 빌 때까지 반복하면서, 현재 노드의 최단 거리를 계산하고, 인접 노드를 업데이트
        while(!pq.isEmpty()){
            Node curNode = pq.poll();

            if(dist[curNode.to] < curNode.weight){
                continue;
            }

            for (int i = 0; i < graph.get(curNode.to).size(); i++) {
                Node adjNode = graph.get(curNode.to).get(i);

                if(dist[adjNode.to] > curNode.weight + adjNode.weight){
                    dist[adjNode.to] = curNode.weight + adjNode.weight;
                    pq.offer(new Node(adjNode.to, dist[adjNode.to])); // 인접 노드를 우선순위 큐에 넣어줌
                }
            }
        }

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

    public static void main(String[] args) {
        int[][] data = {{1, 2, 2}, {1, 3, 3}, {2, 3, 4}, {2, 4, 5}, {3, 4, 6}, {5, 1, 1}};
        dijkstra(5, data, 1);
    }
}

다익스트라의 한계점

다익스트라 알고리즘의 한계점은 음의 가중치를 갖는 간선이 있을 때 정확한 결과를 보장하지 않으며, 또한 그래프의 크기가 크고 간선의 수가 많은 경우에는 성능이 저하될 수 있습니다.

따라서, 다익스트라 알고리즘은 주로 음의 가중치를 갖지 않는 그래프에서 사용되며, 최단 경로를 구하는 데에 많이 활용됩니다.