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

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

1. 개념

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
음수 간선이 없을 때 사용 가능하며, **우선순위 큐(Heap)**를 이용하면 빠르게 계산할 수 있다.

---

2. 작동 방식 요약

1. 시작 노드에서 거리를 0으로 초기화, 나머지는 무한대로 설정
2. 아직 방문하지 않은 노드 중 가장 가까운 노드 선택
3. 선택한 노드를 기준으로 인접한 노드의 거리 업데이트
4. 모든 노드를 방문할 때까지 반복

---

3. C# 예제 코드 (우선순위 큐 사용)

using System;
using System.Collections.Generic;

class Edge
{
    public int To, Cost;
    public Edge(int to, int cost)
    {
        To = to;
        Cost = cost;
    }
}

class Node : IComparable<Node>
{
    public int Vertex, Distance;
    public Node(int v, int d)
    {
        Vertex = v;
        Distance = d;
    }

    public int CompareTo(Node other)
    {
        return Distance.CompareTo(other.Distance);
    }
}

void Dijkstra(int start, List<Edge>[] graph, int[] dist)
{
    int n = graph.Length;
    bool[] visited = new bool[n];
    for (int i = 0; i < n; i++) dist[i] = int.MaxValue;
    dist[start] = 0;

    var pq = new PriorityQueue<Node, int>();
    pq.Enqueue(new Node(start, 0), 0);

    while (pq.Count > 0)
    {
        pq.TryDequeue(out var current, out _);
        int now = current.Vertex;

        if (visited[now]) continue;
        visited[now] = true;

        foreach (var edge in graph[now])
        {
            int cost = dist[now] + edge.Cost;
            if (cost < dist[edge.To])
            {
                dist[edge.To] = cost;
                pq.Enqueue(new Node(edge.To, cost), cost);
            }
        }
    }
}

📌 C# 10 이상에서 PriorityQueue<TElement, TPriority> 사용 가능 (System.Collections.Generic)

---

4. 시간/공간 복잡도

항목	복잡도
시간 복잡도	O(E log V) (우선순위 큐 사용 시)
공간 복잡도	O(V + E)

 

• V: 정점 수
• E: 간선 수

---

5. 특징

• 음수 간선이 없는 경우에만 사용 가능
• 단일 시작점 기준 최단 거리
• BFS보다 복잡하지만 더 정확하고 빠름 (가중치 포함 가능)
• 코딩 테스트에서 그래프 문제에 자주 등장

---

6. 예시

정점: 0, 1, 2, 3  
간선: (0→1, 4), (0→2, 2), (2→1, 1), (1→3, 1), (2→3, 5)

출발: 0 → 도착: 모든 노드  
최단 거리: [0, 3, 2, 4]

---

7. 마무리 요약

• 다익스트라 알고리즘은 가장 널리 쓰이는 최단 경로 알고리즘
• 음수 가중치가 없다면 무조건 사용 가능
• 우선순위 큐를 활용하면 성능을 크게 향상시킬 수 있음
• 실전에서는 BFS vs 다익스트라의 선택이 중요함 (가중치 유무)