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

다익스트라(Dijkstra) 알고리즘은 네비게이션 길 찾기나 네트워크 라우팅 등 실생활에서 가장 많이 활용되는 알고리즘 중 하나다. 그래프 내의 특정 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 것이다.

---

알고리즘 동작 단계

다익스트라는 크게 4단계의 반복으로 이루어진다.

1. 출발점 설정: 시작 노드를 지정하고 해당 노드의 거리를 0으로 설정한다.
2. 거리 배열 초기화: 시작점을 제외한 모든 노드까지의 거리를 아주 큰 값(INF)으로 설정한다.
3. 최단 거리 노드 선택: 아직 방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 선택한다.
4. 경로 갱신: 선택한 노드를 거쳐 인접 노드로 가는 거리와 기존에 저장된 거리를 비교하여 더 짧은 값을 저장한다.

---

구현 방법

다익스트라의 성능은 “가장 가까운 노드를 어떻게 찾는가”에 달려 있다.

• 단순 반복문 사용: 매번 모든 노드를 확인하므로 $O(V^2)$의 시간이 걸린다. (V는 노드의 수)
• 우선순위 큐(PriorityQueue) 사용: 거리가 짧은 노드를 즉시 뽑아낼 수 있어 $O(E \log V)$로 훨씬 빠르다. (E는 간선의 수)
  

C# 코드

using System;
using System.Collections.Generic;

class Solution
{
    public int solution(int N, int[,] road, int K)
    {
        int answer = 0;
        int INF = 10000000; // 충분히 큰 값 설정
        int[] dist = new int[N + 1];
        bool[] visited = new bool[N + 1];

        // 1. 거리 배열 초기화
        for (int i = 1; i <= N; i++) dist[i] = INF;
        dist[1] = 0;

        // 2. 다익스트라 알고리즘 수행
        for (int i = 0; i < N; i++)
        {
            int minDistance = INF;
            int u = -1;

            // 아직 방문하지 않은 노드 중 가장 가까운 노드 선택
            for (int j = 1; j <= N; j++)
            {
                if (!visited[j] && dist[j] < minDistance)
                {
                    minDistance = dist[j];
                    u = j;
                }
            }

            if (u == -1) break; // 더 이상 갈 수 있는 곳이 없음
            visited[u] = true;

            // 선택된 노드(u)를 거쳐가는 경로가 더 짧은지 확인
            for (int r = 0; r < road.GetLength(0); r++)
            {
                int start = road[r, 0];
                int end = road[r, 1];
                int weight = road[r, 2];

                if (start == u && dist[end] > dist[u] + weight)
                {
                    dist[end] = dist[u] + weight;
                }
                else if (end == u && dist[start] > dist[u] + weight)
                {
                    dist[start] = dist[u] + weight;
                }
            }
        }

        // 3. K 시간 이하인 마을 카운트
        for (int i = 1; i <= N; i++)
        {
            if (dist[i] <= K) answer++;
        }

        return answer;
    }
}

---

주의사항

다익스트라 알고리즘에는 한 가지 제약 조건이 있다.

“가중치(거리/시간)에 음수가 있으면 안 된다”
다익스트라는 “현재 가장 짧은 경로를 찾았다면, 그것이 최단 경로다”라는 그리디(Greedy) 원리를 따른다. 하지만 음수 가중치가 있다면, 나중에 더 작은 값이 나타나 기존의 최단 경로 가정을 깨뜨릴 수 있기 때문이다.