다익스트라 최단 거리 알고리즘
특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이며, 음의 간선이 없을 때 정상 동작함.
다익스트라의 알고리즘 과정을 간략이 설명하면 아래와 같다.
1. 출발 노드 설정
2. 최단 거리 테이블을 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 해동 노드를 거쳐 다른 노드로 가능 비용을 계산하여 최단 거리 테이블을 갱신
5. 3, 4 과정을 반복
문제 예시
아래의 그림과 같이 노드들이 주어졌다고 생각해 보자.
1. 출발 노드는 1이다.
2. 1번 노드에서 2번과 4번 노드로 갈 수 있다.
3. 방문 하지 않은 노드중 4번 노드가 짧으니 4번 노드를 선택한다.
4. 4번 노드에서 갈 수 있는 3번 노드와 5번 노드의 거리를 갱신한다.
5. 방문하지 않은 노드중 2, 3, 5중에서 2, 5가 가장 짧으니 2번 노드를 선택한다.
6. 2번 노드에서 4와 3을 갈 수 있는데, 모두 거리를 갱신할 수 없다.
7. 위의 과정을 방문하지 않은 노드를 탐색하면서 갱신해 나간다.
다익스트라 알고리즘의 핵심
- 그리디 알고리즘을 통해 가보지 않은 노드를 선택한 후 인접노드 길이가 기존 길이보다 짧다면 갱신한다. > 추후 해당 노드에 최단 코스를 보장한다.(새치기가 가능하다. )
- 걸어온 길들의 최단거리를 이미 저장해 놓았다. (메모이제이션)
당위성 증명
귀류법으로 진행하자면, 해당 알고리즘이 최단거리를 못찾았다고 가정해보자.
해당 노드의 이름은 T라고 한다. T노드에 대한 다익스트라 알고리즘을 적용하여 T노드의 최단 거리를 확정지을 때 T노드 방문 이전에 방문한 노드 그룹을 A, 아직 방문하지 않은 노드 그룹을 B라고 하자.
체크할 점
- T노드는 시작점이 될 수 없다.
- 잘못되었다고 가정한 다익스트라 알고리즘이 찾아준 T노드의 길이를 구하는데 A그룹만 적용되었다.
- 때문에 B 그룹도 적용된 상태로 T노드의 거리를 체크해야 한다.
A그룹에 마지막으로 추가된 노드를 a B그룹에 처음으로 등장한 노드를 b라고 가정해보자.
우리의 다익스트라 알고리즘은 기존 path --> a --> T 가 가장 빠르다고 말해주었다.
하지만 위의 답은 틀렸으므로 path --> a --> b --> T가 적절하다.
라고 생각하기엔... 뭔가가 이상하다?
핵심 포인트
a의 인접노드는 b, T라고 할 수 있다. 그러나 우리는 항상 거리가 짧은 노드를 선택한다.(그리디 알고리즘) 때문에 b가 T노드 앞에 있다는 것은 b가 A그룹에 속한다는 것인데 이러한 상황은 우리가 가정한 상황과 대치되므로 우리의 가정이 애초에 잘못되었다고 볼 수 있다. (단 해당 노드 거리에 음수가 있다면...? 앞의 말이 전부 말이 된다.)
따라서 다익스트라 알고리즘은 정당하다.
다익스트라 O(V^2) version
단계마다 방문하지 않은 노드중에서 최단 거리 노드를 찾기 위해 순차 탐색한다.
import sys
INF = int(1e9)
# NODE 의 갯수와 EDGE의 갯수 받기
n, m = map(int, sys.stdin.readline().rstrip().split())
# 시작 노드를 받기
start = int(input())
# 인접 리스트 방식으로 그래프 받기
graph = [[] for _ in range(n+1)]
# 방문한 적 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n + 1)
# 거리를 상한으로 모두 초기화
distance = [INF] * (n + 1)
# 모든 간선 정보를 받기
for _ in range(m):
# a노드에서 b노드로 가는 비용이 c
a, b, c = map(int, sys.stdin.readline().rstrip().split())
graph[a].append((b, c))
def get_smallest_node(distance: list[int], visited: list[bool]) -> int:
min_value = INF
index = 0 # 가장 최단 거리가 짧은 노드
for i in range(1, n+1):
# 방문하지 않은 노드 중에서, 최단 거리의 노드를 반환
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def dijkstra(start: int, graph: list[int], distance: list[int], visited: list[bool]):
# 시작 노드에 대해서 초기화
distance[start] = 0
visited[start] = True
for j in graph[start]: # j: [도착 노드, 거리] 시작 노드에 대한 거리를 갱신
distance[j[0]] = j[1]
for i in range(n-1):
# 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
now = get_smallest_node(distance, visited)
visited[now] = True
# 방문한 노드의 인접노드들의 거리를 갱신
for j in graph[now]:
cost = distance[now] + j[1]
# 갱신하려는 거리가 현재 구한 거리보다 작은 경우 갱신
if cost < distance[j[0]]:
distance[j[0]] = cost
return distance
# distance 값을 저장
dist = dijkstra(start, graph, distance, visited)
### 최단 거리 출력
for i in dist[1::]:
if i == INF:
print("INF")
else:
print(i)다익스트라 우선순위 큐로 구현하기
위의 코드에서 get_smallest_node를 우선 순위큐로 대체한다면 아래와 같이 구현이 가능하다.
import sys
import heapq
INF = int(1e9)
# NODE 의 갯수와 EDGE의 갯수 받기
n, m = map(int, sys.stdin.readline().rstrip().split())
# 시작 노드를 받기
start = int(input())
# 인접 리스트 방식으로 그래프 받기
graph = [[] for _ in range(n+1)]
# 거리를 상한으로 모두 초기화
distance = [INF] * (n + 1)
# 모든 간선 정보를 받기
for _ in range(m):
# a노드에서 b노드로 가는 비용이 c
a, b, c = map(int, sys.stdin.readline().rstrip().split())
graph[a].append((b, c))
def dijstra(start: int, graph: list[graph], distance: list[int]) -> list[int]:
q = []
# 시작 노드에 대한 정보를 먼저 q에 삽입하자.
heapq.heappush(q, (0, start)) # q에 dist: 0 , 도착 노드를 튜플 형태로 삽입
distance[start] = 0
# 힙에 처음 노드를 넣음 > 힙에 최소값을 뺌 > 해당 노드를 처리 했는지 먼저 판단
# > 처리하지 않았다면 > 인접 노드들의 정보를 현재 노드와 start 노드 거리 + 현재 노드와 인접노드의 거리
while q:
# 최단 거리의 노드를 꺼내기
dist, now = heapq.heappop(q)
# 방문여부가 가장 중요하다. 방문 여부를 체크하자.
# 방문하지 않았다면 INF 방문했다면 dist가 반드시 작게 된다. (이미 해당 노드에 이미 방문했다면 최소값이 고정된 상태)
if distance[now] < dist:
continue
# 인접 노드들을 체크하기
for i in graph[now]:
nxt_node = i[0]
nxt_dist = i[1] + dist
# 해당 노드를 통과해 인접노드로 가는 거리가 더 짧다면 갱신 및 해당 노드를 힙에다 넣기
if nxt_dist < distance[nxt_node]:
distance[nxt_node] = nxt_dist
heapq.heappush(q, (nxt_dist, nxt_node))
return distance[1::]힙 구조를 이용한 다익스트라 알고리즘 복잡도
heappush: logE
heappop: 1
for i in graph[now]: Edge
따라서 시간 복잡도는 O(ElogE)이다. 여기서 E <= V^2 이므로 최악의 시간 복잡도는 O(ElogV)로 나타낼 수 있다.
일반적인 다익스트라 알고리즘 사용법
노드의 갯수보다 간선의 갯수가 더 많으면 V^2 알고리즘을
노드의 갯수가 10000개가 넘어가면 힙구조를 이용한 알고리즘을 사용하자.
