가중치 그래프

가중치 그래프란?

간선마다 비용(weight)이 붙어 있는 그래프다. 지금까지의 그래프는 "이어져 있다/아니다"만 따졌지만, 현실의 문제는 대개 "얼마나 멀리" 또는 "얼마나 비싸게" 이어져 있느냐를 묻는다.

간선 $(u, v)$ 의 가중치를 $w(u, v)$ 로 적는다.

인접 행렬. $A[u][v]$ 에 가중치를 넣는다. 간선이 없으면 $\infty$ (코드에서는 아주 큰 수)로 둔다. 정점이 $V$ 개면 $O(V^2)$ 의 공간을 쓰므로 간선이 빽빽할 때 유리하다.

A[u][v] = \begin{cases} w(u,v) & (u,v)\text{가 간선일 때} \\ \infty & \text{아닐 때} \end{cases}

인접 리스트. 정점마다 (이웃, 가중치) 쌍을 담는다. 공간이 $O(V+E)$ 라 간선이 성길 때 유리하고, 실제 문제 풀이에서는 대개 이쪽을 쓴다.

python

# 무방향 그래프. 방향 그래프면 한쪽만 넣는다.
graph = [[] for _ in range(n + 1)]
for u, v, w in edges:
    graph[u].append((v, w))
    graph[v].append((u, w))

간선의 가중치가 모두 같을 때만 BFS가 최단거리를 준다. BFS는 "간선을 몇 개 지났나"로 거리를 세기 때문이다. 가중치가 다르면 간선 수가 적은 길이 오히려 더 비쌀 수 있다.

1 \xrightarrow{\ 10\ } 3, \qquad 1 \xrightarrow{\ 1\ } 2 \xrightarrow{\ 1\ } 3

BFS는 간선 하나짜리 위쪽 길(비용 10)을 먼저 찾지만, 실제 최단거리는 아래쪽 길(비용 2)이다. 그래서 가중치 그래프에는 따로 알고리즘이 필요하다.

문제	알고리즘	시간복잡도	음수 간선
한 점에서 모든 점까지	다익스트라	$O(E\log V)$	안 됨
한 점에서 모든 점까지	벨만-포드	$O(VE)$	됨 (음수 순환 탐지)
모든 점 쌍 사이	플로이드-워셜	$O(V^3)$	됨
모든 정점을 잇는 최소 비용	크루스칼 · 프림	$O(E\log E)$	됨

음수 간선이 있으면 다익스트라를 쓸 수 없다. 다익스트라는 "지금까지 확정된 거리는 더 줄지 않는다"를 전제로 정점을 하나씩 확정하는데, 음수 간선이 있으면 나중에 더 짧은 길이 나타날 수 있어 그 전제가 깨진다.

바로 다음 글에서 다익스트라 알고리즘을 다룬다.