다익스트라 알고리즘 Dijkstra Algorithm

본 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있다면 언제든지 피드백을 주시면 감사하겠습니다. 참고로만 활용해주시길 바랍니다.

개요

---

하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

• 어떤 경로도 음수 가중치를 갖지 않는 그래프에서 사용 가능
• 유향/무향 상관이 없다.

다익스트라 알고리즘은 동적 계획법 문제이다.

• 최단 거리는 여러 개의 최단 거리로 이루어져 있으므로 작은 문제가 큰 문제의 부분 집합이다.
• 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용

과정

---

1. 모든 노드의 거리를 큰 수로 초기화하고 시작 노드의 거리를 0으로 초기화
2. 아직 방문하지 않은 노드 중 가장 가중치가 작은 노드 방문
3. 해당 노드를 거쳐 갈 수 있는 노드의 거리가 이전보다 작으면 해당 거리를 갱신
4. 더 이상 방문할 노드가 없을 때까지 2~3 반복

모든 노드의 거리를 큰 수로 초기화하고, 시작 노드(1)의 거리를 0으로 초기화

시작 노드에서 갈 수 있는 노드들의 거리를 갱신 (현재 선택된 노드와 에지는 파란색으로 표시)

아직 방문하지 않은 노드 중 가장 가중치가 작은 노드(2) 방문 및 해당 노드를 거쳐 갈 수 있는 거리 중 최단 거리가 있다면 갱신 (이미 방문한 노드는 빨간색으로 표시)

반복

반복

반복

더 이상 방문할 노드가 없고, 노드 1에서 모든 노드로 가는 최단 거리를 구하였음

시간 복잡도

---

$V$: 노드의 숫자, $E$: 간선의 숫자

초기 알고리즘의 시간 복잡도는 $O(V^2)$

• $V$ 크기의 최단거리 1차원 배열을 매번 반복문을 이용하여 검사
• 총 $O(V)$번에 걸쳐서 모든 인접노드를 검사하기에 $O(V^2)$

최소 힙(우선순위 큐)으로 구현 시 $O((V+E)log V)$

• $VlogV+ElogV=(V+E)logV$
• 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 $O(VlogV)$
  • 최대 $V$개의 노드가 들어가 있는 우선순위 큐에서 삭제 연산 $(logV)$
• 각 노드마다 이웃한 노드의 최단거리를 갱신하는데 $O(ElogV)$
  • 각 노드에 연결된 최대 $E$개의 에지에서 우선순위 큐에 삽입 연산 $(logV)$

코드

---

# 다익스트라 알고리즘 최소 힙 구현
import heapq, sys
from typing import List
input = sys.stdin.readline
INF = int(1e9)

def dijkstra(graph: List, start: int) -> List:
    distance = [INF] * len(graph)
    pq = [(0, start)]
    
    distance[start] = 0

    while pq:
        dist, now = heapq.heappop(pq)
        if distance[now] < dist: continue

        for next_node, cost in graph[now]:
            new_cost = dist + cost

            if new_cost < distance[next_node]:
                distance[next_node] = new_cost
                heapq.heappush(pq, (new_cost, next_node))

    return distance
    
def main():
    v, e = map(int, input().split())
    start = int(input())
    
    graph = [[] for _ in range(v + 1)]

    for _ in range(e):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))

    result = dijkstra(graph, start)

    for i in range(1, v + 1):
        print(result[i], end=' ') if result[i] != INF else print("INF", end=' ')

if __name__ == "__main__":
    main()
    
'''
Test Case
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 3
4 3 3
4 5 1
5 3 1
5 6 2

0 2 3 1 2 4

5 7
1
1 2 100
1 3 2
2 4 1
2 5 1
3 4 3
4 5 5
5 2 3

7 7
1
1 2 1
1 4 3
2 3 100
2 5 10
3 7 1
4 5 4
5 3 3
'''

참고

• https://ko.wikipedia.org/wiki/데이크스트라_알고리즘