최단 경로

특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘

말 그대로 가장 짧은 경로를 찾는 알고리즘. 크게 2가지 경우로 나누면,

1. 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우
2. 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우

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

특정한 노드에서 출발해 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘.

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

각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장해두고 그 리스트를 계속해서 갱신해나가는 방식. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다는 점에서 그리디 알고리즘으로 볼 수 있다.

파이썬에서 구현은 우선순위 큐를 사용해야 한다.
계속해서 갱신하는 최단 거리 테이블(1차원 리스트) 말고, 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 우선순위 큐를 사용한다.

우선순위 값을 표현할 때는 (거리, 노드)으로 묶어서 사용하고, 이를 우선순위 큐에 넣었다가 다시 꺼내게 되면 항상 거리가 짧은 노드가 먼저 나오게 된다.

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 매우 큰 수

# n개의 노드, m개의 간선, 시작 노드 start
n, m = map(int, input().split())
start = int(input())

graph = [[] for i in range(n)]
distance = [INF] * (n + 1) # 노드의 인덱스가 1부터 시작하기 때문

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

def dijkstra(start):
	q = []
    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)

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘. 2차원 리스트에 '최단 거리' 정보를 저장하는 방식으로 인해 매번 $O(N^2)$의 시간이 소요된다.

0. 연결된 간선은 그 값을 채우고, 연결되지 않은 간선은 '무한'으로, 자기 자신으로 가는 비용은 0으로 초기화한다.
1. 현재 확인하고 있는 노드를 제외한 $N-1$개의 노드 중에서 서로 다른 $(A, B)$쌍을 선택한다.
2. $A$에서 $B$로 가는 비용과 $A$에서 현재 노드를 거쳐 $B$로 가는 비용을 비교해서 더 작은 값으로 $A$에서 $B$로 가는 최소 비용을 갱신한다.
3. 모든 노드에 대해 1번과 2번을 반복한다.

점화식으로는 아래와 같이 나타낼 수 있다.

구현은 다이나믹 프로그래밍으로 한다.

INF = int(1e9)

# n개의 노드, m개의 간선
n = int(input())
m = int(input())

# 최초에 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
	for b in range(1, n + 1):
    	if a == b:
        	graph[a][b] = 0

# 나머지 연결된 간선들 비용 할당
for _ in range(m):
	a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n + 1):
	for a in range(1, n + 1):
    	for b in range(1, n + 1):
        	graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])