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

1. 설명

1) 최단 경로 문제

- 가중 그래프와 두 개의 정점 u, v가 주어졌을 때, u와 v 사이의 무게의 합이 최소인 경로를 구하는 문제

- 최단 경로길이: 간선들의 무게 합

2) 속성

- 최단 경로의 부분 경로 또한 최단 경로

- 출발 정점으로부터 다른 모든 정점에 이르는 최단 경로 트리가 존재 (단일점 최단 경로)

3) 최소신장트리와의 차이점

- 방향 그래프에서도 정의

- 무방향 그래프에 음의 무게를 가진 간선이 있으면 부정

4) 시간복잡도

- 정점 수: V, 간선 수: E

 

- 기본 알고리즘의 시간 복잡도: O(V^2)

- 우선순위 큐 사용시 시간 복잡도: O(ElogV)

---

2. 알고리즘 수행 과정

1) 출발 정점부터 각 정점까지의 거리를 담은 최단 거리 테이블(dist)을 INF 값으로 초기화한다.

 

2) 출발 정점부터 시작하여 현재 탐색하고 있는 노드(v)의 인접노드(u)의 거리를 갱신한다.

 - 현재 탐색하고 있는 노드(v)의 출발 정점으로 까지의 거리 + v와 u의 거리

 - 기존의 u의 출발 정점으로 까지의 거리

 - 위 두 개를 비교하여 더 작은 값을 인접 노드(u)의 거리(dist[u])로 갱신한다.

 

3) 현재 탐색하고 있는 노드의 탐색하지 않은 인접 노드 중 가장 거리가 짧은 노드를 선택하여 방문한다.

 - 이 때 우선순위 큐를 사용하여 가장 거리가 짧은 노드를 선택한다.

 

4) 2 ~ 3의 과정을 모든 정점에 대한 탐색이 끝날 때까지 반복한다.

---

3. 알고리즘 수행 과정 예시

1) 최단 거리 테이블(dist)을 INF 값으로 초기화

- 출발점 부터 각 정점까지의 거리를 담은 dist 테이블의 모든 값을 INF로 초기화해주고, 출발점에 해당하는 1번 노드의 dist[1] 값은 0으로 초기화 해준다.

 

2) 1번 노드와 연결된 노드(u)의 dist[u] 값을 갱신

- 1번 노드와 연결된 노드(u)의 dist 값을 원래의 dist[u]와 dist[1] + (1번 노드와 u 노드와의 간선의 가중치)를 비교해 더 작은 값으로 갱신한다. dist[u] = min(dist[u], dist[1] + (1번 노드 - u번 노드 연결))

- dist[2] = min(inf, dist[1] + 1) = 1- dist[3] = min(inf, dist[1] + 2) = 2- dist[4] = min(inf, dist[1] + 3) = 3

 

3) 1번 노드와 연결된 방문하지 않은 노드 중 dist값이 가장 작은 2번 노드 선택

- 2번 노드와 연결된 노드(u)의 dist 값을 원래의 dist[u]와 dist[2] + (2번 노드와 u 노드와의 간선의 가중치)를 비교해 더 작은 값으로 갱신한다. dist[u] = min(dist[u], dist[2] + (2번 노드 - u번 노드 연결))

- dist[4] = min(3, dist[2] + 1) = 2

- dist[5] = min(inf, dist[2] + 4) = 5

 

4) 위 과정 반복

- 가장 짧은 거리의 노드를 선택하고 그 노드와 연결된 노드의 dist 값을 갱신 시켜주는 과정을 반복하면 아래의 그림과 같이 최단 경로를 찾을 수 있다.

---

4. Python구현

- 파이썬으로 구현했을 때 코드 (시간복잡도: O(ElogV))

- dist[node] < d : 해당 노드에 대한 방문 체크(현재 갱신이 되지 않은 dist 값이 온 상태)

from heapq import heappush, heappop
import sys

def dijkstra(start):
    dist[start] = 0
    q = []
    heappush(q, (0, start))

    while q:
        d, node = heappop(q)
    
    	# 방문 체크
        if dist[node] < d:
            continue

        for next in edge[node]:
            cost = next[0] + d
            # 거리가 더 짧아질 경우 거리 갱신
            if dist[next[1]] > cost:
                dist[next[1]] = cost
                heappush(q, (cost, next[1]))
    


n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())


edge = [[] for _ in range(n + 1)]
dist = [1e9] * (n + 1)

for _ in range(m):
    u, v, w = map(int, sys.stdin.readline().strip().split())
    edge[u].append((w, v))

start= int(sys.stdin.readline().strip())

dijkstra(start)

print(dist)