Dijkstra 다익스트라

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

가중치가 있는 그래프에서 한 정점 ( Vertex ) 에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다.

"다익스트라는 최단 경로를 찾는 알고리즘이다"

에츠허르 다익스트라 ( Edsger W. Dijkstra ) 가 고안한 알고리즘이다.

다익스트라 알고리즘을 확장시킨 알고리즘이 A* 알고리즘이다.

• 네비게이션에서 최단 거리 길 찾기
• 게임에서 AI 가 "가장 짧은 길"로 이동
• 네트워크 라우팅 경로 계산

 

핵심 아이디어

가장 가까운 노드부터 차근차근 확정해 나아가는 방식 ( Greedy 방식 )

1. 시작점의 거리를 0 으로 설정
2. 아직 방문하지 않은 노드 중 현재까지 거리값이 가장 작은 노드를 선택
3. 이 노드를 통해 갈 수 있는 주변 노드들의 거리값을 갱신 ( Relaxation )
4. 모든 노드를 방문할 때까지 반복

 

핵심 개념 ( 자료구조 포함 )

거리 배열 ( distance[ ] )

각 노드까지의 현재 최소 비용을 기록

distance[] = {0, ∞, ∞, ∞, ...}

 

 

우선 순위 큐 ( Priority Queue , Min - Heap )

• 거리값이 가장 작은 노드를 빠르게 꺼내기 위해 사용한다
• 다익스트라에서 가장 중요한 자료구조
• O(log N) 이기 때문에 전체 성능이 크게 향상된다

 

Relaxation ( 거리 갱신 )

새로운 경로가 더 짧다면 교체한다

if ( distance[next] > distance[current] + cost )
    distance[next] = distance[current] + cost

 

 

동작 예시

그래프 : 

A 에서 시작한다고 가정

A --2-- B
A --5-- C
B --1-- C

Step 1
distance: A=0, B=∞, C=∞
→ 제일 작은 A 선택

 

 

Step 2

A 통해 B, C 갱신

 

• B = 2
• C = 5

 

Step 3

다음 가장 작은 거리 = B(2)

• B 통해 C = 2 + 1 = 3
• 기존 C(5) 보다 작으므로 3 으로 교체

 

 

Step 4

마지막 남은 C 선택 → 종료

 

 

최종 결과

A → B : 2
A → C : 3

 

 

시간 복잡도

• 우선순위 큐 사용 : O(E log V)
• E = 간선 수 , V = 노드 수
• 그래프에서 최단 경로를 구하는 알고리즘 중 가장 효율적이다 ( 음수 가중치 제외 )

 

의사 코드 ( Pseudo Code )

Graph 는 모든 노드와 노드 간의 거리 , 이웃 노드에 관한 정보를 포함한다

Source 는 출발할 노드를 의미한다

prev[ ( node ) ]는 출발지까지 가장 빠르게 갈 수 있다고 계산된 이웃 노드를 가리킨다. 

즉, 출발지부터 목적지까지의 경로가 아니라, 목적지부터 출발지까지의 경로를 기록한다.
dist[ ( node ) ]는 출발지부터 현재 node까지의 cost 값을 의미한다.

function Dijkstra(Graph, Source):
 
    dist[source] ← 0                       // 소스와 소스 사이의 거리 초기화 --출발지와 출발지의 거리는 당연히 0--
    prev[source] ← undefined               // 출발지 이전의 최적 경로 추적은 없으므로 Undefined

    create vertex set Q                    // 노드들의 집합 Q(방문되지 않은 노드들의 집합) 생성 시작

    for each vertex v in Graph:            // Graph안에 있는 모든 노드들의 초기화
        if v ≠ source:                     // V 노드가 출발지가 아닐 경우(출발지를 제외한 모든 노드!)
            dist[v] ← INFINITY             // 소스와 V노드 사이에 알려지지 않은 거리 --얼마나 먼지 모르니까-- = 무한값 (모든 노드들을 초기화하는 값)
            prev[v] ← UNDEFINED            // V노드의  최적경로 추적 초기화
        add v to Q                         // Graph에 존재하고 방금 전 초기화된 V 노드를 Q(방문되지 않은 노드들의 집합)에 추가

//요약하자면, Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함.
    
    while Q is not empty:                  // Q 집합이 공집합 아닐 경우, 루프 안으로!
        u ← vertex in Q with min dist[u]   // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작
        remove u from Q                    // U 노드를 방문한 것이므로 Q집합에서 제거
        
        for each neighbor v of u:          // U의 이웃노드들과의 거리 측정
            alt ← dist[u] + length(u, v)   // 출발지 노드 부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리
                                           // = source to U + V to U = source to U
            if alt < dist[v]:              // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우
                dist[v] ← alt              // V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈
                prev[v] ← u                // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈

    return dist[], prev[]                  // 계산된 거리값과 목적지를 리턴

 

 

예시 코드

using NUnit.Framework;
using UnityEngine;
using System.Collections.Generic;
using UnityEngine.Rendering;

class DijkstraNode
{
    public int Index;              // ABCD, 0123 번호
    public Vector2 Pos;            // 해당 노드의 좌표
    public float Distance;         // 시작점으로부터 현재 노드까지의 누적 거리
    public DijkstraNode Parent;    // 경로 추적용 부모 노드

    public DijkstraNode(int index, Vector2 pos, float distance, DijkstraNode parent = null)
    {
        Index = index;
        Pos = pos;
        Distance = distance;
        Parent = parent;
    }
}

public class DijkstraExample : MonoBehaviour
{
    private void Start()
    {
        int n = 4; // 노드 개수
        int startIndex = 0; // 시작 노드 인덱스 A
        int goalIndex = 3; // 목표 노드 인덱스 B

        // 각각의 노드에 좌표 설정해주기
        Vector2[] positions = new Vector2[4]
        {
            new Vector2(0, 0), // A
            new Vector2(1, 0), // B
            new Vector2(0, 1), // C
            new Vector2(1, 1) // D
        };

        // 그래프 구성
        List<(int to, float cost)>[] graph = new List<(int to, float cost)>[n];
        for (int i = 0; i < n; i++)
        {
            graph[i] = new List<(int to, float cost)>();
        }

        // 비용 정보 추가
        graph[0].Add((1, 1)); // A → B (1)
        graph[0].Add((2, 4)); // A → C (4)
        graph[1].Add((2, 2)); // B → C (2)
        graph[1].Add((3, 6)); // B → D (6)
        graph[2].Add((3, 3)); // C → D (3)

        // 각 노드까지의 최소 거리 저장 배열
        float[] distances = new float[n];
        for (int i = 0; i < n; i++)
        {
            distances[i] = float.MaxValue;
        }

        // 시작 위치
        distances[startIndex] = 0;

        // 방문 여부 저장 배열
        bool[] visited = new bool[n];

        // 탐색 대기 리스트
        var openList = new List<DijkstraNode>();

        // 시작 지점 추가
        openList.Add(new DijkstraNode(startIndex, positions[startIndex], 0));

        // 탐색 루프
        while (openList.Count > 0)
        {
            // 거리 기준으로 정렬
            openList.Sort((a, b) => a.Distance.CompareTo(b.Distance));

            // 최소 거리 노드 선택
            var current = openList[0];

            // 선택한 노드는 탐색 대상에서 제외
            openList.RemoveAt(0);

            // 방문한 노드면 스킵하기
            if (visited[current.Index])
            {
                continue;
            }

            // 방문 처리
            visited[current.Index] = true;

            // 목표 노드 도착시 경로 복원
            if (current.Index == goalIndex)
            {
                var path = new List<int>();
                var temp = current;

                while (temp != null)
                {
                    path.Add(temp.Index);
                    temp = temp.Parent;
                }

                // D → C → B → A

                // 역순으로 들어갔으니 뒤집기
                path.Reverse();

                // A → B → C → D

                Debug.Log("Dijkstra Path" + string.Join(" -> ", path));
                Debug.Log("Distance" + current.Distance);

                break;
            }
            
            foreach (var neighbor in graph[current.Index])
            {
                // 이미 방문한 노드는 패스
                if (visited[neighbor.to])
                {
                    continue;
                }

                // 현재 노드까지의 거리 + 간선 비용
                float t = current.Distance + neighbor.cost;

                // 더 짧은 경로 발견시
                if (t < distances[neighbor.to])
                {
                    distances[neighbor.to] = t;

                    // 새로운 노드 추가
                    openList.Add(new DijkstraNode(neighbor.to, positions[neighbor.to], t, current));
                }
            }
        }
    }
}