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

🚀 다익스트라 알고리즘(Dijkstra Algorithm)이란?

다익스트라 알고리즘은 그래프에서 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 네덜란드의 컴퓨터 과학자 **에츠허르 다익스트라(Edsger W. Dijkstra)**가 개발했어요.

"GPS가 길 찾을 때 최단 경로를 계산하는 기본 원리!"
바로 다익스트라 알고리즘입니다.

 

 

다익스트라 알고리즘

---

✅ 주요 특징

• 가중치가 있는 그래프에서 사용됨
• 단, 모든 **간선의 가중치가 0 이상(음수 불가)**이어야 함
• 하나의 시작 노드로부터 모든 노드까지의 최소 비용을 구함

---

🎯 동작 방식 요약

1. 시작 정점의 거리는 0, 나머지는 무한대(∞)로 초기화
2. 방문하지 않은 노드 중 가장 거리가 짧은 노드 선택
3. 해당 노드를 거쳐 갈 수 있는 이웃 노드의 거리 계산 후 업데이트
4. 모든 노드를 방문할 때까지 2~3단계를 반복

다익스트라 알고리즘 예시

---

🧠 시간 복잡도

자료구조시간 복잡도

배열 사용	O(V²)
우선순위 큐(힙)	O(E log V)

 

• V: 정점 수
• E: 간선 수
  → **우선순위 큐(PriorityQueue)**를 사용하면 성능이 매우 향상됩니다.

---

🧪 Java 코드 예시 (우선순위 큐 사용)

import java.util.*;

public class DijkstraExample {
    
    static class Node implements Comparable<Node> {
        int index, distance;

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

        // 거리 기준으로 오름차순 정렬
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }

    static final int INF = (int)1e9;
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int[] dist;

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

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            int nowIdx = now.index;
            int nowDist = now.distance;

            if (dist[nowIdx] < nowDist) continue;

            for (Node next : graph.get(nowIdx)) {
                int cost = dist[nowIdx] + next.distance;
                if (cost < dist[next.index]) {
                    dist[next.index] = cost;
                    pq.offer(new Node(next.index, cost));
                }
            }
        }
    }

    public static void main(String[] args) {
        int n = 6; // 노드 수
        int start = 1;
        dist = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
            dist[i] = INF;
        }

        // 예시 간선 추가
        graph.get(1).add(new Node(2, 2));
        graph.get(1).add(new Node(3, 5));
        graph.get(2).add(new Node(3, 3));
        graph.get(2).add(new Node(4, 4));
        graph.get(3).add(new Node(4, 2));
        graph.get(4).add(new Node(5, 1));
        graph.get(5).add(new Node(6, 2));

        dijkstra(start);

        // 결과 출력
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF) {
                System.out.println(i + "번 노드: 도달 불가");
            } else {
                System.out.println(i + "번 노드까지의 최단 거리: " + dist[i]);
            }
        }
    }
}

 

---

🖥️ 출력 예시 (간선 구성에 따라 달라짐)

 

 

1번 노드까지의 최단 거리: 0  
2번 노드까지의 최단 거리: 2  
3번 노드까지의 최단 거리: 5  
4번 노드까지의 최단 거리: 7  
5번 노드까지의 최단 거리: 8  
6번 노드까지의 최단 거리: 10

---

📌 정리

항목내용

알고리즘 이름	다익스트라 알고리즘
목적	하나의 정점에서 모든 정점까지 최단 거리 계산
조건	음의 가중치 불가, 연결된 그래프
성능	힙 사용 시 O(E log V)
사용 예	GPS, 네트워크 경로, 최단시간 계산 등

 

---

✅ 관련 개념도 알고 싶다면?

• 벨만–포드 알고리즘: 음수 간선이 있는 경우에도 사용 가능
• 플로이드–워셜 알고리즘: 모든 정점에서 모든 정점으로의 거리 계산
• A* 알고리즘: 다익스트라보다 빠른 휴리스틱 기반 경로 탐색