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

※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다.

※ 해당 포스팅은 하기 출처들을 참조하였습니다.

- 존 캐리, 코딩 테스트를 위한 자료구조와 알고리즘 with C++, 도서출판 길벗, 2022

 

 

 

 이번 포스팅에서는 가중치가 있는 그래프의 순회에 사용할 수 있는 다익스트라 알고리즘에 대해 알아보겠습니다.

1. 개요

 다익스트라 알고리즘은 그림 1과 같이 간선의 가중치가 존재하는 그래프를 순회하는데 사용하는 알고리즘으로, 시작 정점부터 시작하여 모든 정점을 순회하며 각 정점에 시작 정점으로부터의 최단 거리를 기록합니다.

 

그림 1. 가중치가 있는 그래프

 다음은 그림 1의 그래프에 0번 정점을 시작점으로 다익스트라 알고리즘을 적용하는 과정을 도식화 한 것입니다.

 

그림 2. 다익스트라 알고리즘 예시

 우선 시작점은 0으로, 시작점을 제외한 모든 정점은 무한대(혹은 아주 큰 값)으로 초기화합니다. 우선 다음에 방문할 정점을 선택하는데, 아직 방문하지 않은 정점 중 가장 값이 낮은 정점을 선택합니다. 맨 처음의 경우 시작점이 0으로 가장 작으므로 시작점을 방문하게 됩니다. 방문한 정점은 따로 기록하고, 연결된 정점들을 확인하여 (현재 정점의 값 + 연결된 정점과의 거리)값이 연결된 정점의 값보다 작다면, 해당 값으로 갱신합니다.

 

 이 후

정점 선택 및 값 갱신 과정(그림 2의 3~4번)

을 반복합니다. 위 예시에서는 방문한 0번 정점을 제외하고 값이 가장 낮은 1번 정점으로 이동한 후, 값 비교를 실행하여 5번 정점의 값을 35로 갱신했습니다. 2번 정점의 경우 현재 위치의 값 + 해당 정점까지의 거리(10 + 15)보다 이미 저장된 값(20)이 더 작으므로 갱신하지 않습니다. 해당 과정을 반복하여 모든 정점을 방문하고 나면 각 정점에 저장된 값이 시작점(0번 정점)부터의 최단거리가 됩니다.

 

 

 

2. 코드 구현

 다음은 C#으로 작성한 그림 1의 그래프에 다익스트라 알고리즘을 적용하는 예제입니다.

static int[,] graph =
{
    { -1, 10, 20, 35, -1, -1, -1 },
    { 10, -1, 15, -1, -1, 25, -1 },
    { 20, 15, -1, 10, -1, -1, -1 },
    { 35, -1, 10, -1, 05, -1, -1 },
    { -1, -1, -1, 05, -1, -1, 10 },
    { -1, 25, -1, -1, -1, -1, 15 },
    { -1, -1, -1, -1, 10, 15, -1 }
};

static void Main(string[] args)
{
    Dijkstra(0);
}

static void Dijkstra(int start)
{
    int size = graph.GetLength(0);
    bool[] visited = new bool[size];
    int[] nodes = new int[size];

    // 모든 정점을 아주 큰 값으로 초기화
    Array.Fill(nodes, int.MaxValue);
    // 시작점은 0으로 초기화
    nodes[start] = 0;

    while(true)
    {
        // 가장 가까운 정점 찾기
        int closest = int.MaxValue;
        int cur = -1;
        for (int i = 0; i < size; i++)
        {
            // 이미 방문했거나 한번도 값이 갱신되지 않은 정점이라면 스킵
            if (visited[i] || nodes[i] == int.MaxValue)
                continue;
            // 현재 값보다 멀다면 스킵
            if (nodes[i] >= closest)
                continue;

            closest = nodes[i];
            cur = i;
        }

        // 대상을 찾지 못했다면 종료
        if (cur == -1)
            break;

        visited[cur] = true;

        // 정점 값 갱신
        for (int next = 0; next < size; ++next)
        {
            // 이미 방문했거나 연결되지 않은 정점은 스킵
            if (visited[next] || graph[cur, next] < 0)
                continue;

            int sum = nodes[cur] + graph[cur, next];
            if (sum < nodes[next])
                nodes[next] = sum;
        }
    }
    // 출력
    for(int i = 0; i < nodes.Length; i++)
        Console.WriteLine($"{i}번째 노드 값: {nodes[i]}");
}

사진 1. 다익스트라 예제

 그래프는 2차원 배열로 표현하였으며 연결된 정점은 가중치로, 연결되지 않은 경우 -1로 초기화하였습니다. DFS, BFS와 마찬가지로 방문여부를 저장할 visited 배열을 선언했고, 추가로 각 정점의 값을 저장할 nodes 배열을 선언하였습니다.

 

 시작점을 제외한 정점은 int.MaxValue로, 시작점은 0으로 초기화 한 뒤 반복문을 돌며 아직 방문하지 않은 정점 중 기록된 값이 가장 낮은 정점을 찾아 방문합니다. 이후 인접한 정점들을 체크하며 (현재 정점값 + 연결된 정점까지의 거리) 값이 연결된 정점의 값보다 작다면 해당 값으로 갱신합니다. 모든 정점을 방문할때까지 해당 과정을 반복합니다.

 

 또한 상기 예제에서 코드를 약간 추가하여 시작점부터 특정 정점까지 이동하는 최단거리를 탐색할 수도 있습니다.

// 길찾기 정보 저장용
int[] parent = new int[size];
parent[start] = start;

// 정점 값 갱신
for (int next = 0; next < size; ++next)
{
    // 이미 방문했거나 연결되지 않은 정점은 스킵
    if (visited[next] || graph[cur, next] < 0)
        continue;

    int sum = nodes[cur] + graph[cur, next];
    if (sum < nodes[next])
    {
        nodes[next] = sum;
        parent[next] = cur; // 어디서 이동했는지 저장
    }
}

// 부모 배열을 통해 최단경로 찾기
List<int> road = new List<int>(size);
int now = 6;
while(parent[now] != now)
{
    road.Add(now);
    now = parent[now];
}
road.Add(now);
// 출력
for(int i = road.Count - 1; i > 0; i--)
    Console.Write($"{road[i]} > ");
Console.WriteLine(road[0]);

사진 2. 다익스트라를 통한 최단루트 탐색

 우선 경로를 저장할 배열을 선언한 뒤, 시작점 인덱스의 값을 시작점으로 초기화합니다. 그리고 위 로직에서 정점값을 갱신하는 부분에 parent[next] 값을 cur로 저장하여 next 정점에 어느 정점에서 이동해왔는지를 기록합니다. 다익스트라 연산을 끝낸 후, 목표 정점부터 시작하여 parent 배열을 돌며 경로를 어느 정점을 통해 이동했는지 리스트에 저장하여 출력하면 사진 2와 같은 결과를 얻을 수 있습니다(단, 목표 정점부터 출발하여 순회하므로 경로를 저장한 리스트를 반전하거나 뒤에서부터 출력해야 합니다).

 

 

 

3. 장점과 단점

 다익스트라 알고리즘은 BFS, DFS에서 다루지 못했던 간선에 가중치가 있는 그래프의 순회에 사용할 수 있습니다. 또한 시작 정점으로부터 각 정점까지의 최단거리를 저장하므로, 길찾기 로직에 자주 사용되는 알고리즘입니다.

 

 단, 다익스트라 알고리즘은 그래프의 가중치가 모두 양수일때만 적용할 수 있습니다. 다익스트라 알고리즘의 과정을 살펴보면 항상 가장 가까운 정점으로 이동하는 일종의 그리디(Greedy) 알고리즘임을 알 수 있습니다. 그런데 가중치에 음수가 존재할 경우, 그리디 방식으로 이동하며 저장한 값이 최소값임을 보장할 수 없게 됩니다. 음수 가중치 그래프에 적용할 수 있는 알고리즘으로는 벨만 포드(Bellman-Ford) 알고리즘 등이 있습니다.

 

 또한 다음에 방문할 노드를 찾는 과정이 단순히 모든 정점을 체크하므로 해당 부분이 다소 비효율적이라고 할 수 있습니다. 위 코드 예제를 다시 확인해보면 다음에 방문할 정점을 찾기 위해 반복문을 돌며 모든 정점값을 확인하고 있음을 알 수 있습니다. 이 부분만으로 이미 O(n)의 시간복잡도 이므로 노드의 갯수가 많아질수록 속도가 느려지기 쉽습니다.

// 가장 가까운 정점 찾기
// 노드의 수만큼 반복(O(n))
int closest = int.MaxValue;
int cur = -1;
for (int i = 0; i < 6; i++)
{
    if (visited[i] || nodes[i] == int.MaxValue)
        continue;
    if (nodes[i] >= closest)
        continue;

    closest = nodes[i];
    cur = i;
}

 

 해당 부분을 개선한 것이 A* 알고리즘입니다. 정점의 값을 (현재 위치까지의 비용 + 목표 정점까지의 예상 비용)으로 계산하고 우선순위 큐(Priority Queue)에 저장하여, 다음에 방문할 가장 낮은 비용의 정점을 신속하게 탐색합니다. A* 알고리즘에 관한 내용은 다음 포스팅에서 다루도록 하겠습니다.