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

⭐ 다익스트라 알고리즘

길찾기 알고리즘 중의 하나로 최단경로를 구할 수 있는 알고리즘입니다.

그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 거리를 구합니다.

 

실생활에서는 내비게이션, 도로 교통망 최적화, 인터넷 네트워크 라우팅 등에 사용되며,

게임에서는 몬스터 AI, 넓은 거리 맵 생성, 길찾기 및 이동 시스템 등에 사용됩니다.

 

 

탐색 방식

---

 

● 아래 링크에서 다양한 길찾기 알고리즘의 작동 방식을 직접 실행해볼 수 있습니다.

    ○ https://qiao.github.io/PathFinding.js/visual/

다익스트라 과정

 

● 위의 그래프에서 A → D 노드로 가는 탐색 과정을 살펴보겠습니다.

 

 

● A에서 시작하기 때문에 A를 방문처리 해줍니다.

● 나머지 노드에는 방문하지 않았으므로 아직 거리 비용을 모릅니다.

● 방문하지 않은 노드들은 정확한 거리를 모르기 때문에 매우 큰 수를 가지고 있습니다.

    ○ 최소 비용을 구하기 때문에 임의의 큰 수를 할당해놓음

 

 

 

● A에 인접한 B와 C의 비용을 계산합니다.

● 아직 A노드에서 이동하지 않았으므로 탐색 노드는 추가하지 않습니다.

● A에서 가장 가까운 B 노드로 이동합니다.

 

 

 

● A → C의 거리비용이 4였고, A → B → C의 거리 비용이 3이므로 C까지의 비용을 3으로 변경합니다.

● B 노드를 탐색 처리합니다.

● B에 인접하고 탐색하지 않은 노드인 C, D를 탐색 대상에 추가합니다.

 

 

 

● 위와 같은 과정을 반복하며 C 노드로 이동합니다.

 

 

 

● 목표 지점에 도달하면 탐색이 종료됩니다.

 

 

장점과 단점

---

장점

● 우선순위 큐를 이용해 효율적인 탐색이 가능합니다.

● 시작점에서 모든 노드로의 최단 경로 탐색이 가능합니다.

● 구현이 간단하며 직관적입니다.

 

단점

● 음수 가중치가 있는 경우에는 사용이 불가능합니다. → 벨만-포드 알고리즘으로 해결 가능

● 그래프(경우의 수)가 큰 경우 성능 저하가 발생합니다.

 

 

 

 

다익스트라 알고리즘 코드

---

● 위와 같은 그래프에서 A → D 최단거리를 구하는 코드입니다.

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

public class DijkstraNode
{
    public int index;               //번호
    public Vector2 pos;             //해당 노드의 좌표
    public float distance;          //시작점으로 부터 현재 노드까지의 누적 거리
    public DijkstraNode parent;     //경로 추적용 부모 노드

    public DijkstraNode(int index, Vector2 pos, float distance, DijkstraNode parent = null)
    {
        this.index = index;
        this.pos = pos;
        this.distance = distance;
        this.parent = parent;
    }
}

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

        //각각의 노드에 좌표 설정해주기
        Vector2[] positions = new Vector2[4]
        {
            new Vector2(1, 0),      //A
            new Vector2(0, 1),      //B
            new Vector2(0, 0),      //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];

        //탐색 대기 리스트
        List<DijkstraNode> 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

                //역순으로 뒤집기, A - B - C - D
                path.Reverse();

                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));
                }
            }
        }
    }
}

● 해당 코드에서는 리스트를 이용하여 노드들을 관리했지만, 우선순위 큐를 이용한다면 중간에 따로 정렬해주는 과정이 필요없어지기 때문에 더 효율적인 구조로 만들 수 있습니다.