다익스트라 알고리즘 (Dijkstra's Algorithm)

📌  정의

다익스트라 알고리즘은 가중치가 있는 그래프에서 특정 시작 노드로부터 다른 모든 노드까지의 최단경로를 구하는 알고리즘

 

📌  특징

- 모든 간선의 가중치가 양수 (음수 가중치를 가진 그래프는 벨만-포드 알고리즘)

- 각 노드를 방문하면서 해당 노드까지의 최단 거리를 계속 갱신 

 

📌  알고리즘 동작 과정 

1. 시작 노드의거리를 0으로 설정하고, 다른 노드의 거리를 무한대로 초기화

2. 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택 

3. 해당 노드와 인접한 노드의 거리 값을 갱신 

 - 새거리 = 현재 노드거리 + 간선 가중치

 - 이때 새거리<기존 거리이면 새거리로 갱신 

4. 모든 노드를 방문할 때까지 위 과정 반복 

 

✏️  예제

아래 그림과 같은 그래프가 주어졌을 때, 노드 1에서 다른 모든 노드까지의 최단 거리 구하기.

 

1. 인접 리스트를 사용하여 그래프 생성

2. 우선순위 큐 ( PriorityQueue ) 를 이용하여 거리 기준 오름차순으로 정렬

3. 거리 배열에 시작 노드로부터 각 노드까지의 최단거리 저장

4. 인접 노드에 대해 새로운 최단 거리를 계산하고, 기존 거리보다 작으면 갱신

 

 

import java.util.*;

public class DijkstraExample {
    public static void main(String[] args) {
        // 그래프 생성
        int V = 4; // 노드 수
        List<List<Node>> graph = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 추가 (노드 번호, 가중치)
        graph.get(1).add(new Node(2, 4));
        graph.get(1).add(new Node(3, 2));
        graph.get(2).add(new Node(3, 1));
        graph.get(2).add(new Node(4, 5));
        graph.get(3).add(new Node(4, 8));

        // 다익스트라 알고리즘 실행
        int[] distances = dijkstra(1, V, graph);

        // 결과 출력
        System.out.println("최단 거리:");
        for (int i = 1; i <= V; i++) {
            System.out.println("1 -> " + i + ": " + distances[i]);
        }
    }

    public static int[] dijkstra(int start, int V, List<List<Node>> graph) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        //java의 우선순위큐 생성 
        int[] distances = new int[V + 1];
        Arrays.fill(distances, Integer.MAX_VALUE);
        //배열의 모든 요소를 Integer.MAX_VALUE로 초기화
        distances[start] = 0;
        //현재 노드는 0 으로 설정

        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll(); //우선순위 가장 높은 값 꺼내기 (가장 가까운 노드)
            int currentNode = current.node;
            int currentDist = current.distance;

            // 이미 처리된 노드는 건너뛰기
            if (currentDist > distances[currentNode]) continue;

            for (Node neighbor : graph.get(currentNode)) {
				//새거리 구하기
				int newDist = distances[currentNode] + neighbor.distance;

				//새거리가 기존거리보다 작으면 갱신 
                if (newDist < distances[neighbor.node]) {
                    distances[neighbor.node] = newDist;
                    pq.add(new Node(neighbor.node, newDist));
                }
            }
        }

        return distances;
    }

    // 우선순위 큐에 사용할 노드 클래스
    static class Node implements Comparable<Node> {//compareTo메서드 내부적으로 동작 
        int node;
        int distance;

        Node(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node o) {//정렬 기준 정의
            return this.distance - o.distance; // 거리 기준 오름차순
        }
    }
}

 

 

💻 요점 

1. 거리 초기값을 최대값으로 설정

2. priorityQueue 사용하여 오름차순 정렬 

3. 기존거리 > 새거리이면 갱신