다익스트라 최단 경로 알고리즘

전체 코드

int[,] adj = new int[6, 6]
{
    { -1, 15, -1, 35, -1, -1 },
    { 15, -1, 5, 10, -1, -1 },
    { -1, 5, -1, -1, -1, -1 },
    { 35, 10, -1, -1, 5, -1 },
    { -1, -1, -1, 5, -1, 5 },
    { -1, -1, -1, -1, 5, -1 },
};
public void Dijikstra(int start)
{
    bool[] visited = new bool[6]; // 방문 하였느냐
    int[] distance = new int[6];
    int[] parent = new int[6];


    // 큰 값으로 바꿔줌
    Array.Fill(distance, Int32.MaxValue);
    distance[start] = 0;
    parent[start] = start;

    while (true)
    {

        //제일 좋은 후보를 찾는다(가장 가까이 있는)
        // 가장 유력한 후보의 거리와 번호를 저장한다.
        int closest = Int32.MaxValue;
        int now = -1; // 나중에 후보를 찾았는지 못찾았는지 여부를 체크하기 편하게 만든다.
                    

        for (int i = 0; i < 6; i++)
        {
            // 이미 방문한 정점은 스킵
            if (visited[i]) continue;
            // 아직 예약된적이 없거나 기존에 후보보다 멀리 있으면 스킵
            if (distance[i] == Int32.MaxValue || distance[i] >= closest) continue;

            // 여태껏 발견한 가장 좋은 후보의 의미기 때문에 정보 갱신
            closest = distance[i];
            now = i;

            // 배열에서 큰 값을 찾고 싶을때 갱신하면서 바꾸는 패턴등을 자주 사용한다.

        }
        // 다음 후보가 하나도 없다 -> 종료
        if (now == -1) break;

        // 제일 좋은 후보를 찾았으니 방문
        visited[now] = true;

        // 방문한 정점과 인접한 정점들을 조사해서 
        // 상황에 따라 발견한 최단거리를 갱신한다.

        for (int next = 0; next < 6; next++)
        {
            if (adj[now, next] == -1) continue;
            if (visited[next]) continue;

            // 새로 조사된 정점의 최단거리를 계산한다.
            int nextDist = distance[now] + adj[now, next];

            // 기존에 발견한 최단거리가 새로 조사된 최단거리보다 크면 정보를 갱신한다.
            if (nextDist < distance[next])
            {
                distance[next] = nextDist;
                parent[next] = now;

            }
        }


    }
}

static void Main(string[] args)
{
	Graph graph = new Graph();
	graph.Dijikstra(6);
}

📌 다익스트라 알고리즘이란?

✔️ 핵심 개념

• 그래프에서 특정 시작 정점에서 모든 정점까지의 최단 경로를 구하는 알고리즘입니다.
• 가중치가 있는 그래프에서 사용할 수 있으며, BFS와 다르게 가중치가 다를 때도 최적의 경로를 찾을 수 있습니다.
• 우선순위 큐(Priority Queue, Min-Heap) 를 사용하면 성능을 향상할 수 있습니다.

✔️ BFS와의 차이점

	BFS	다익스트라
간선 가중치	모두 동일	각기 다름
방문 순서	단순 가까운 순서	최단 거리 순서
자료구조	큐 (Queue)	우선순위 큐 (PriorityQueue)
핵심 개념	거리 없이 레벨 순회	비용 고려 최단 경로

---

📊 그래프 표현 방법

다익스트라 알고리즘을 적용할 그래프는 인접 행렬 또는 인접 리스트 로 표현할 수 있습니다.

✔️ 인접 행렬 예시

int[,] adj = new int[6, 6]
{
    { -1, 15, -1, 35, -1, -1 },
    { 15, -1, 5, 10, -1, -1 },
    { -1, 5, -1, -1, -1, -1 },
    { 35, 10, -1, -1, 5, -1 },
    { -1, -1, -1, 5, -1, 5 },
    { -1, -1, -1, -1, 5, -1 },
};

• -1 : 연결되지 않은 정점
• 양수 값 : 정점 간 거리(가중치)

---

💻 다익스트라 알고리즘 구현

1️⃣ 데이터 초기화

bool[] visited = new bool[6];          // 방문 여부
int[] distance = new int[6];           // 최단 거리 저장
int[] parent = new int[6];             // 경로 추적용 (부모 정점 기록)
Array.Fill(distance, Int32.MaxValue);  // 아직 모르는 거리 = 무한대
distance[start] = 0;                   // 출발지는 자기 자신과의 거리가 0
parent[start] = start;                 // 출발지의 부모는 자기 자신

✅ 초기 상태
| 정점 | 방문 여부 | 거리 | 부모 |
|---|---|---|---|
| 0 | false | 0 | 0 |
| 1~5 | false | 무한대 | 없음 |

---

2️⃣ 가장 가까운 정점 찾기

int closest = Int32.MaxValue;
int now = -1;

for (int i = 0; i < 6; i++)
{
    if (visited[i]) continue;  // 이미 방문한 정점 제외
    if (distance[i] >= closest) continue;  // 더 가까운 정점만 선택

    closest = distance[i];
    now = i;
}

• BFS와 다르게 단순 순서가 아닌 최단 거리 우선으로 방문합니다.

---

3️⃣ 정점 방문 처리

if (now == -1) break;  // 더 이상 방문할 정점 없음 = 종료
visited[now] = true;   // 방문 처리

---

4️⃣ 인접 정점들의 거리 갱신

for (int next = 0; next < 6; next++)
{
    if (adj[now, next] == -1) continue;  // 연결 안된 정점 제외
    if (visited[next]) continue;        // 이미 방문한 정점 제외

    int nextDist = distance[now] + adj[now, next];  // 현재 정점 거쳐가는 거리 계산

    if (nextDist < distance[next])  // 더 짧은 경로 발견
    {
        distance[next] = nextDist;  // 최단 거리 갱신
        parent[next] = now;         // 경로 추적용 부모 갱신
    }
}

• distance[next]: 지금까지 발견된 최단 거리
• nextDist: now를 거쳐가는 새로운 거리
• 더 짧은 경로가 발견되면 갱신 (이것이 최단 경로의 핵심)

---

🚀 다익스트라 전체 코드 (우선순위 큐 미사용)

using System;

namespace Algorithm
{
    class Graph
    {
        int[,] adj = new int[6, 6]
        {
            { -1, 15, -1, 35, -1, -1 },
            { 15, -1, 5, 10, -1, -1 },
            { -1, 5, -1, -1, -1, -1 },
            { 35, 10, -1, -1, 5, -1 },
            { -1, -1, -1, 5, -1, 5 },
            { -1, -1, -1, -1, 5, -1 },
        };

        public void Dijkstra(int start)
        {
            bool[] visited = new bool[6];
            int[] distance = new int[6];
            Array.Fill(distance, Int32.MaxValue);
            int[] parent = new int[6];

            distance[start] = 0;
            parent[start] = start;

            while (true)
            {
                int closest = Int32.MaxValue;
                int now = -1;

                for (int i = 0; i < 6; i++)
                {
                    if (visited[i]) continue;
                    if (distance[i] == Int32.MaxValue || distance[i] >= closest) continue;

                    closest = distance[i];
                    now = i;
                }

                if (now == -1) break;
                visited[now] = true;

                for (int next = 0; next < 6; next++)
                {
                    if (adj[now, next] == -1) continue;
                    if (visited[next]) continue;

                    int nextDist = distance[now] + adj[now, next];

                    if (nextDist < distance[next])
                    {
                        distance[next] = nextDist;
                        parent[next] = now;
                    }
                }
            }
        }
    }
}

---

🚖 다익스트라의 단점

• 현재 코드는 O(V²) 의 시간복잡도를 가짐.
• 우선순위 큐(PriorityQueue)를 사용하면 O(E log V)로 성능을 향상할 수 있음.
• 다익스트라는 음수 가중치가 포함된 그래프에서는 사용할 수 없음.
  • 이를 해결하려면 벨만-포드 알고리즘을 사용해야 함.

---