최단 경로 문제
- 최단 경로 문제는 각 간선의 가중치 합이 최소가 되는 두 정점 사이의 경로를 찾는 문제이다.
- 이때 가중치는 거리나 시간과 같은 이동 비용에 해당한다.
BFS
- 간선의 가중치가 모두 1인 두 노드 사이의 최단 경로를 찾는데 사용한다.
- 인접 리스트로 구현 시 시간 복잡도는 O(V+E)이고, 인접 행렬로 구현 시 시간 복잡도는 O(V^2)이다.
구현 (경로 추적 포함)
from collections import deque
import sys
sys.setrecursionlimit(200000)
n, k = map(int, input().split())
time = [-1] * 200001
time[n] = 0
path = [-1] * 200001
path[n] = n
q = deque()
q.append(n)
while q:
now = q.popleft()
for next in [now + 1, now - 1, 2 * now]:
if 0 <= next <= 200000 and time[next] == -1:
time[next] = time[now] + 1
path[next] = now
q.append(next)
print(time[k])
def find_path(n, k):
if n != k:
find_path(n, path[k])
print(k, end=" ")
find_path(n, k)
다익스트라 (Dijkstra)
- 간선의 가중치가 양수인 방향 그래프에서 한 정점으로부터 다른 모든 정점 사이의 최단거리를 구하는 알고리즘
- 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디 알고리즘 중 하나로, 노드 주변을 탐색할 때 BFS를 이용한다.
- 프림 알고리즘과 비슷하게 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 가지고 더한다.
- 그래프 내에 음의 가중치를 갖는 간선이 없는 경우에만 사용가능하다.
시간 복잡도
- 배열로 구현하면 전체 수행시간은 O(V^2)
- 우선순위 큐를 최소힙으로 사용해서 구현하면 전체 수행시간은 O((V+E)*logV)
- 만약 그래프에 간선이 아주 많다면 배열로 구현하는 것이 낫지만, 그래프에 간선이 많지 않다면 최소힙을 사용한 방법이 더 좋다.
구현 (경로 추적 포함)
import heapq
n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
dist = [-1] * (n + 1)
trace = [[] for _ in range(n + 1)]
start, end = map(int, input().split())
q = []
heapq.heappush(q, (0, start))
dist[start] = 0
trace[start].append(start)
while q:
cost, now = heapq.heappop(q)
if dist[now] != -1 and dist[now] < cost:
continue
for nxt, nxt_cost in graph[now]:
nxt_cost += cost
if dist[nxt] == -1 or nxt_cost < dist[nxt]:
dist[nxt] = nxt_cost
heapq.heappush(q, (nxt_cost, nxt))
# 경로 갱신
trace[nxt] = []
for p in trace[now]:
trace[nxt].append(p)
trace[nxt].append(nxt)
print(dist[end])
print(len(trace[end]))
print(*trace[end])
플로이드-워셜
- 그래프에서 모든 정점 사이의 최단 거리를 한 번에 찾는 알고리즘으로, 가중치가 음수인 간선은 가질 수 있으나 가중치의 합이 음수가 되는 사이클이 존재하면 안된다.
- 먼저 한 정점에서 다른 정점으로 이동하는 간선 가중치를 인접 행렬에 채워넣고 중간 경유지를 만들어, 바로 가는 것보다 중간 경유지를 거쳐서 가는 것이 빠르다면 최단거리를 갱신한다. (DP)
- 시간 복잡도는 O(V^3)
구현 (경로 추적 포함)
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
INF = sys.maxsize
def find_path(i, j):
if trace[i][j] == 0:
return []
k = trace[i][j]
return find_path(i, k) + [k] + find_path(k, j)
n = int(input())
m = int(input())
dist = [[INF] * (n + 1) for _ in range(n + 1)]
trace = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dist[i][i] = 0
for _ in range(m):
a, b, c = map(int, input().split())
dist[a][b] = min(dist[a][b], c)
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
trace[i][j] = k
for i in range(1, n + 1):
for j in range(1, n + 1):
if dist[i][j] != INF:
print(dist[i][j], end=" ")
else:
print(0, end=" ")
print()
for i in range(1, n + 1):
for j in range(1, n + 1):
if dist[i][j] == 0 or dist[i][j] == INF:
print(0)
continue
path = [i] + find_path(i, j) + [j]
print(len(path), end=" ")
print(*path)
벨만-포드 알고리즘
- 간선의 가중치가 음수 혹은 양수인 가중 방향 그래프가 주어졌을 때, 특정 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘
- V-1 번의 반복동안 시작점에서 각 정점까지의 최단 경로의 오차를 점차 줄여나가며, 이 과정에서 DP를 이용해 사용했던 데이터를 재사용한다.
- 구성 간선들의 가중치 총합이 음수인 사이클의 포함 여부를 판단할 수 있다.
- 음수 사이클 탐지를 포함한 V번의 순회와, 각 순회마다 그래프 내의 간선을 모두 순회하므로 시간 복잡도는 O(V*E)
음수 사이클 탐지
INF = int(1e9)
def bellman_ford(start):
dist[start] = 0
# 간선 개수만큼 반복
for i in range(v):
for j in range(e):
node = edges[j][0]
nxt = edges[j][1]
cost = edges[j][2]
if dist[node] != INF and dist[nxt] > dist[node] + cost:
dist[nxt] = dist[node] + cost
if i == v - 1:
return True
return False
v, e = map(int, input().split())
edges = []
dist = [INF] * (v + 1)
for _ in range(e):
a, b, c = map(int, input().split())
edges.append((a, b, c))
cycle = bellman_ford(1)
if cycle:
print(-1)
else:
for i in range(2, v + 1):
if dist[i] == INF:
print(-1)
else:
print(dist[i])