다익스트라 알고리즘

다익스트라 알고리즘

다익스트라 알고리즘은 특정 노드(start 노드) 에서 나머지 경로로 갈 수 있는 최단경로를 구하는 알고리즘이다.

실제로 네비게이션등에 사용되는 기본 알고리즘이며 이 알고리즘을 최적화 시켜 사용하게 된다.

게임에서 자동으로 npc 등을 찾아가게 하는, 퀘스트 fetch 등의 기능은 이 다익스트라 알고리즘을 베이스로 하는 A* 알고리즘을 사용하는 경우가 있다고 한다.

A를 사용하는 이유는 다익스트라의 현실 적용이 매우 어렵기 때문이다. 당장에 네트워크 같은 디지털적인 공간이 아닌, 현실의, 사람이 사는 공간을 생각해보자. 사람이 다닐 수 있는 "거리"는 명백히 아날로그하다. 이것들을 전부 노드화시키기에는 그 수가 엄청나게 많아질 수 있다. 그렇다면 탐색해야 하는 공간도 그만큼 커지게 되고, 시간 복잡도 역시 아득히 커질 것이다. 또한 어찌어찌 잘 노드화시켜서 다익스트라를 사용할 수 있는 상황을 만들어서 경로를 발견했다고 치자. 그렇게 탐색한 경로가 자동차 정체 구간, 출근길 등 다양한 변수로 인해 오히려 더 느려질 수 있는 경우도 발생하기 마련이다. 이러한 변수 때문에 A 알고리즘을 사용하는 것이다. 그리고 A를 발전시킨 형태가 D(Dynamic A*)알고리즘인데, 현세대의 대부분의 차량 내비게이션은 이를 활용한다고 보면 된다

다익스트라 알고리즘의 조건

• 그래프 내의 간선 가중치가 음수 값이 없어야 한다.
  • 그래프 내에 간선 가중치에 음수값이 있을 경우, 반드시 싸이클이 발생하기 때문에, 경로 자체가 무너진다.
    다익스트라 알고리즘은 경로를 이동할 수록 이동거리가 늘어난다는 전제조건을 내포하고 있기 때문에,(최소한 0) 가중치가 음수값이 나오면 안 된다.
  • 그래프는 유향 그래프, 무향 그래프 모두 적용 가능하다. 다만 그 방향마다 가중치가 부여되어야 한다.

다익스트라 알고리즘의 원리

• Greedy 알고리즘과, 다이나믹 프로그래밍 기법이 섞여있다.

  • 그리디 : 가장 가중치가 작은 간선부터 탐색
  • DP : 탐색 과정에서 발생한 최단거리를 기록하여 그 값을 이용해 최단거리를 계속 갱신

  그리디 알고리즘이 다익스트라 알고리즘 성능에 큰 영향을 끼치진 않을 것 같다. 왜냐하면 어차피 최종노드까지의 모든 경로를 탐색하게 되기 때문에, 그리디하게 알고리즘을 종료하지는 않기 때문이다.

구현

다익스트라 알고리즘을 구현하는 방법은 두 가지가 있다. 기본적으로 다익스트라 알고리즘은 현재 노드에서 연결된 가장 짧은 거리의 노드를 탐색해야 하는데, 이 과정을 선형적으로 하는지O(n), 힙을 통해 우선순위큐를 구현하는지O(logN)의 두 가지가 있다.
하지만 시간을 줄일 수 있는데 안 좋은 방법을 선택할 필요는 없으니 우선순위큐를 이용한 구현을 한다.

1. 각 Node에 도달하는 최소 거리를 기억하기 위한 배열 distance를 생성하고, 무한대 값으로 초기화

2. Start Node에서 해당 Node까지의 거리를 정렬 기준으로 하는 Min Heap 생성

3. Start Node를 Min Heap에 삽입 (자기 자신까지의 거리는 0)

4. Min Heap에 Node가 있는 동안 반복

5. Min Heap에서 Node를 하나 꺼낸다.

6. Min Heap에 기록된 거리가 distance에 저장된 해당 Node까지의 거리보다 길면 건너뛴다.

import heapq

def dijkstra(start, graph):
    n = len(graph)
    heap = []
    heapq.heapify(heap)
    distances = [float('inf')] * n

    heapq.heappush(heap, (0, start))
    distances[start] = 0

    while heap:
        dist, node = heapq.heappop(heap)

        if distances[node] < dist:
            continue
        adj_list = graph[node]
        for adj_node, adj_dist in adj_list:
            new_dist = dist + adj_dist
            if distances[adj_node] > new_dist:
                distances[adj_node] = new_dist
                heapq.heappush(heap, (new_dist, adj_node))
    return distances

형태가 bfs와 유사하다. 실제로도 노드에서 뻗어 나가는, 방식이 bfs와 유사하다. 다른 점은 bfs는 queue 에 넣어서 모든 노드를 순차적으로 탐색한다는 것과, 다익스트라는 이 queue가 우선순위 큐 여서 항상 최단거리부터 탐색한다는 것.