Dijkstra

다익스트라 알고리즘은 다이나밍 프로그램을 활용한 최단 경로(shortest path) 탐색 방법이다.
그래프에서 시작점부터 다른 모든 지점까지의 최단 경로를 찾는데 사용한다.

1. 특징

• '탐욕적인 방법(greedy method)'을 사용하여 가장 낮은 가중치를 누적하여 최단 경로를 찾는 것
• 음의 가중치를 포함하지 않는다.
• 네트워크 라우팅, 지도의 경로 찾기, 운송망 설계 등 다양한 분야에서 활용된다.

2. 구현 방법

1. 출발 노드를 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장
3. 방문하지 않은 노드 중에서 가장 비용 적은 노드 선택
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용 갱신
5. 3 ~ 4번을 반복

예시) 아래 이미지에서 1 부터 다른 모든 노드로 가는 최단 경로를 구할 때,

1. 처음의 각 2,3,4 로의 최단거리는 3,6,7 이다. (한 번의 이동이 갖는 가중치)
2. 그중 노드 2의 비용이 제일 적으므로 (3) 2를 선택,
3. 그 뒤 3 으로 가는 비용이 1-3 보다 1-2-3 으로 갈때의 비용이 더 저렴하므로, 3으로 가는 최소 비용을 4로 갱신한다. 즉, 현재까지 알고 있던 최단 경로를 계속 비교해가며 갱신함
4. 이 과정을 다른 노드에도 모두 적용한다.

2.1. 구현1 - 순차 탐색

그런데, 위에 방법으로 하면 거리 테이블의 앞에서부터 찾아내야 하므로 노드의 개수만큼 순차 탐색을 수행 해야한다.
따라서, 노드 개수가 N개이면, 순차 탐색 수행으로 시간 복잡도는 (N-1)xN = O(N^2)의 시간이 걸린다.
요 방법은 정점의 갯수는 많고, 간선은 적을 때 비효율적이라 비추비추~

2.2. 구현2 - 우선순위 큐

거리 값을 우선순위 큐, 최소 힙으로 구현하면 매번 루트 노드가 최소 거리를 가지는 노드가 된다.

우선순위 큐를 시작 노드로부터 가장 가까운 노드 기준으로 한다. 이를 사용하면 방문 여부 기록도 필요 없다.
기존 최단 거리보다 크다면 무시하는 것으로 지나치면 된다. 만약 기존 최단거리보다 더 작은 값을 가지는 노드가 있다면, 그 노드와 거리를 우선순위 큐에 넣는다.

이 방법으로 하면 시간 복잡도는, 간선의 수를 E(Edge), 노드의 수를 V(Vertex)라고 했을 때 O(E logV)가 된다.

아래는 파이썬 코드

import heapq

def dijkstra(graph, start):
    # 최단 경로 저장을 위한 dict, 모든 노드에 대해 무한대로 초기화
    distances = {node: float('inf') for node in graph}
    distances[start] = 0  # 시작 노드의 경로 비용은 0으로 설정
    queue = []
    heapq.heappush(queue, [distances[start], start])  # 우선순위 큐에 시작 노드를 넣음

    while queue:  # 큐가 비어있지 않는 동안
        current_distance, current_node = heapq.heappop(queue)

        if distances[current_node] < current_distance:  # 현재 노드의 거리가 이미 처리된 거리보다 작다면
            continue

        for adjacent, weight in graph[current_node].items():  # 인접 노드와 가중치
            distance = current_distance + weight

            # 기존의 최단 경로보다 짧은 경로를 찾은 경우
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])  # 갱신된 거리와 인접 노드를 큐에 추가

    return distances

# 예제 그래프
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

# 알고리즘 실행
dijkstra(graph, 'A')

# 결과
{'A': 0, 'B': 1, 'C': 3, 'D': 4}

---

참고 자료

23. 다익스트라(Dijkstra) 알고리즘
[알고리즘] 다익스트라(Dijkstra) 알고리즘
Python으로 다익스트라(dijkstra) 알고리즘 구현하기