최단 경로

• 가장 짧은 경로를 찾는 알고리즘(길 찾기)
• 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다.
• 그리디와 다이나믹 프로그래밍 알고리즘이 그대로 적용된다.

최단 거리 알고리즘 3가지
1. 다익스트라 최단 경로 알고리즘
2. 플로이드 워셜
3. 벨만 포드 알고리즘

다익스트라 최단 경로 알고리즘

그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

• 기본적으로 그리디 알고리즘이다.
• 음의 간선이 없을 때 정상적 동작 가능하다.
• 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신

알고리즘 원리

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않는 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
   -> 그리디 알고리즘과 유사
5. 3번과 4번을 반복한다.

다익스트라 알고리즘을 구현하는 2가지 방법

방법1. 구현하기 쉽지만 느리게 동작하는 코드
방법2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드
- 방법 2를 정확히 이해하고 구현할 수 있어야 한다.

방법1. 간단한 다익스트라 알고리즘

• 시간 복잡도 : $O(V^2)$ (V는 노드 개수)
  • $O(V)$번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색
  • 이후 단계마다 '방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 리스트의 모든 원소를 확인(순차 탐색)한다.
• 전체 노드 개수가 5,000개 이하라면 문제 해결이 가능하지만, 노드 개수가 10,000개가 넘는다면 이 코드로는 해결하기 어렵다 => 방법2 사용

import sys
input = sys.stdin.readline
INF = int(1e9)    # 무한을 의미하는 값. 10억

# n: 노드 개수, m: 간선의 개수
n, m = map(int, input().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 = map(int, input().split())
    
    # c : a번 노드에서 b번 노드로 가는 비용
    graph[a].append((b, c))

# 방문하지 않은 노드 중, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
	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):
	# 시작 노드를 초기화
    distance[start] = 0
    visited[start] = True
    
    for j in graph[start]:
    	distande[j[0]] = j[1]
    
    # 시작 노드를 제외한 전체 (n-1)개의 노드에 대해 반복
    for i in range(n-1):
    	# 현재 최단 거리가 가장 짧은 노드를 방문
        now = get_smallest_node()
        visited[now] = True
        
        # 현재 노드와 연결된 다른 노드 확인
        for j in graph[now]:
        	cost = distance[now] + j[1]
            
            # 현재 노드를 거쳐 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]:
            	distance[j[0]] = cost
                
 # 다익스트라 알고리즘 수행
 dijkstra(start)
 
 # 모든 노드로 가기 위한 최단 거리 출력
 for i in range(1, n+1):
 	# 도달할 수 없는 경우, 무한이라고 출력
    if distance[i] == INF:
    	print("INFINITY")
    
    # 도달할 수 있는 경우, 거리 출력
    else:
    	print(distance[i])

---

step1 : 출발 노드가 선택된다.

노드 번호	1	2	3	4	5	6
거리	0	무한	무한	무한	무한	무한

step2 : 1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다.

노드 번호	1	2	3	4	5	6
거리	0	2(=0+2)	5(=0+5)	1(=0+1)	무한	무한

step3 : 가장 최단 거리인 4번 노드가 선택된다.

4번 노드에서 갈 수 있는 노드는 3번과 5번이다.

• 1 -> 4 -> 3 : 4
• 1 -> 4 -> 5 : 2

기존의 3번, 5번 값보다 작기 때문에 리스트를 갱신한다.

노드 번호	1	2	3	4	5	6
거리	0	2	4(=1+3)	1	2(=1+1)	무한

step4 : 다음으로 2번 노드가 선택된다.

2번과 5번 노드까지의 최단 거리가 2로 같은데, 일반적으로 번호가 작은 노드를 먼저 선택한다.

• 1 -> 2 -> 3 : 5

기존 3번 노드의 최단 거리 4보다 크기 때문에 값이 갱신되지 않는다.

노드 번호	1	2	3	4	5	6
거리	0	2	4	1	2	무한

step5 : 5번 노드가 선택된다.

5번을 거치면 3번과 6번 노드로 갈 수 있다.

• 1 -> 4 -> 5 -> 3 : 2 + 1 = 3
• 1 -> 4 -> 5 -> 6 : 2 + 2 = 4

노드 번호	1	2	3	4	5	6
거리	0	2	3(=1+1+1)	1	2	4(=1+1+2)

step6 : 3번 노드를 선택한다.

3번 노드는 2번과 6번으로 갈 수 있다.

• 1 -> 4 -> 5 -> 3 -> 2 : 3 + 3 = 6
• 1 -> 4 -> 5 -> 3 -> 6 : 3 + 5 = 8

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

step7 : 마지막으로 6번 노드를 선택한다.

6번은 다음으로 이동할 노드가 없으므로 유지

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

사실 앞서 선택된 노드들은 이미 최단 거리가 완전히 선택된 노드이므로 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다. 따라서, 마지막 노드 6번은 확인할 필요가 없다. 6번을 거칠때 이미 나머지 5개 노드의 최단 거리들이 확정된 상태이므로 더 이상 태이블이 갱신될 수 없기 때문이다.

---

방법2. 개선된 다익스트라 알고리즘

• 최악의 경우 : $O(ElogV)$를 보장 (V: 노드 수, E: 간선 수)
• 힙(Heap) 자료구조 사용

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# n : 노드 수, m : 간선 수
n, m = map(int, input().split())
# 시작 노드 번호 입력받기
start = int(input())

# 각 노드 연결 정보를 담은 리스트
graph = [[] for i in range(n+1)]
# 최단 거리 테이블을 무한으로 초기화
distance = [INF] * (n+1)

# 모든 간선 정보 입력
for _ in range(m):
	# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
	a, b, c = map(int, input().split())
    graph[a].append((b, c))

# 다익스트라 알고리즘 구현
def dijkstra(start):
	
	q = []
    
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정해 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    # 큐가 비어 있지 않다면
    while q:
    	# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
    	dist, now = heapq.heappop(q)
        
        # 현재 노드가 이미 처리된 적 있는 노드라면 무시
        if distance[now] < dist:
        	continue
        
        # 현재 노드와 연결된 다른 인접 노드들을 화인
        for i in graph[now]:
        	cost = dist + i[1]
        	# 현재 노드를 거쳐, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
            	distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
 
 # 다익스트라 알고리즘 수행
 dijkstra(start)
 
 # 모든 노드로 가기 위한 최단 거리를 출력
 for i in range(1, n+1):
 	# 도달할 수 없는 경우, 무한이라고 출력
   	if distance[i] == INF:
      print("INFINITY")
    # 도달할 수 있는 경우, 거리 출력
	else:
    	print(distance[i])
        

step1 : 1번 노드가 출발 노드

출발 노드를 제외한 모든 노드의 최단 거리를 무한으로 설정하고, 우선순위 큐에 1번 노드를 넣는다.

노드 번호	1	2	3	4	5	6
거리	0	무한	무한	무한	무한	무한

우선순위 큐 (거리, 노드)	(거리: 0, 노드: 1)

step2 : 1번 노드를 거쳐 다른 노드로 가는 비용을 계산

노드 번호	1	2	3	4	5	6
거리	0	2(=0+2)	5(=0+5)	1(=0+1)	무한	무한

우선순위 큐 (거리, 노드)	(1, 4) (2, 2) (5, 3)

step3 : 4번 노드를 방문 한다.

현재 최단 거리가 가장 짧은 노드는 4
4번 노드에서 갈 수 있는 노드는 3번과 5번이다.

노드 번호	1	2	3	4	5	6
거리	0	2	4(=1+3)	1	2(=1+1)	무한

우선순위 큐 (거리, 노드)	(2, 2) (2, 5) (4, 3) (5, 3)

step4 : 다시 2번 노드에 대해 처리

우선순위 큐 젤 위의 값이 (2, 2)이므로 2번 노드에 대해 처리
현재 최단 거리를 더 짧게 갱신할 수 있는 방법이 없기 때문에 다음으로 넘어간다.

노드 번호	1	2	3	4	5	6
거리	0	2	4	1	2	무한

우선순위 큐 (거리, 노드)	(2, 5) (4, 3) (5, 3)

step5 : 5번 노드에 대해 처리

5번 노드에서는 3번과 6번 노드로 갈 수 있다.

• 5 > 3 : 2 + 1 = 3
• 5 > 6 : 2 + 2 = 4

노드 번호	1	2	3	4	5	6
거리	0	2	3(=2+1)	1	2	4(=2+2)

우선순위 큐 (거리, 노드)	(3, 3) (4, 3) (4, 6) (5, 3)

step 6 : (3, 3)과 (3, 4) 대해 다시 처리

위와 마찬가지로 이미 지난 노드는 테이블이 갱신되지 않으며 그대로 유지

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

우선순위 큐 (거리, 노드)	(4, 6) (5, 3)

step7 : 6번 노드에 대해 처리

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

우선순위 큐 (거리, 노드)	(5, 3)

step8 : (5, 3)에 대해 다시 처리

이미 처리된 노드이므로 무시한다.

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

우선순위 큐 (거리, 노드)

PriorityQueue와 heapq 는 데이트 개수가 N개일 때, 하나의 데이터를 삽입 및 삭제할 때 시간복잡도는 $O(logN)$ 이다.
개선된 다익스트라 코드는 PriorityQueue보다 통상적으로 더 빠르게 동작하는 heapq를 사용하였다.