📍 최단 경로 문제
그래프 이론에서 빠질 수 없는 것이 최단 경로 문제이다.
이 문제를 해결하는 데에는 크게 세 가지 방법이 있는데,
세 방식의 차이와 적용할 수 있는 문제 상황에 대해 글로 정리해보고자 한다.
참고로 네트워크의 일부 라우팅 방식 또한 최단 경로 알고리즘에 근간을 두고 있다.
Link State라우팅 방식은 다익스트라 알고리즘을 기반으로 하고,
Distance Vector라우팅 방식은 벨만-포드 알고리즘을 기반으로 한다.
(*정보처리기사 시험에 출제되는 내용)
1. 다익스트라 (Dijkstra) 알고리즘
그래프 상에서 하나의 노드로부터 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다.
즉, 가중치 그래프에서 가중치의 합이 최소가 되는 경로를 찾는 방식이다.
다익스트라 알고리즘은 모든 간선이 양의 가중치를 가질 때에만 적용된다.
간선에 음의 가중치가 포함될 경우 플로이드-워셜이나 벨만-포드 알고리즘을 사용해야 한다.
동작 원리
일종의 dp로 볼 수 있다.
- 시작점을 기준으로 간선의 가중치 합 테이블을 만든다.
이때 연결되지 않은 노드에 대해서는 비교를 위해 무한대(INF) 처리 - 연결된 노드를 순회하며 가중치의 최소값을 업데이트한다.
- 이때 값을 업데이트하는 과정에서
(지금까지의 최소 거리 + 직전 간선과의 가중치) vs (해당 노드까지의 직선 가중치) 를 비교해 더 작은 값으로 업데이트해준다.
시간복잡도
알고리즘을 이용해 단순 순회시 최악의 경우 O(V^2) 라는 시간복잡도를 가진다.
따라서 방문하지 않은 노드 중 가중치가 가장 작은 노드를 빠르게 찾기 위해 우선순위 큐를 사용하면 O((V+E)logV)의 시간복잡도를 가지게 된다. (V: 노드 수, E: 간선 수)
구현 (Python)
import heapq
# INF = float('inf')
# table = [INF] * (n + 1) # 시작 노드로부터의 가중치 memoization 테이블
# adj = [[] for _ in range(n+1)] # 인접 리스트 생성 -> 값으로 초기화
def dijkstra(start):
q = []
heapq.heappush(q, (0, start)) # 우선순위 큐에 현재의 가중치(0)와 시작 노드 삽입
table[start] = 0 # 시작 노드의 가중치는 0으로
while q:
# 우선순위 큐를 사용하면 넣어놓은 값 중 최단거리가 최소인 노드를 알아서 꺼내줌
cost, v = heapq.heappop(q)
# 이미 방문했던 노드라면 (이미 최단거리로 업데이트 된 경우) 지나침
if table[v] < cost:
continue
# 인접 노드 확인
for cur_node, cur_cost in adj[v]:
new_cost = cost + cur_cost
# 해당 노드를 거쳐가는 것이 현재 기록된 거리보다 짧을 경우 갱신
if table[cur_node] > new_cost:
table[cur_node] = new_cost
heapq.heappush(q, (new_cost, cur_node))
2. 플로이드-워셜 (Floyd-Warshall) 알고리즘
벨만-포드와 다익스트라가 한 노드에서 그 노드를 제외한 나머지 노드로의 거리를 구하는 알고리즘이었다면,
플로이드-워셜 알고리즘은 모든 노드 간의 최단거리를 구할 수 있는 알고리즘이다.
동작 원리
플로이드-워셜 또한 인접한 노드간의 최단거리를 구해가면서 테이블을 갱신한다는 점에서 일종의 dp에 해당한다.
세 정점 i, j, k가 있다고 했을 때 경유와 다이렉트 중,
즉 (i->k) + (k->j) 와 (i->j) 중 가중치가 최소가 되는 값으로 계속 업데이트해준다는 의미다.
구현은 i, j, k에 대한 3중 for문을 통해 간단하게 해결할 수 있다.
다만 각 단계마다 거쳐가는 중간 노드 k가 핵심인데,
중간 노드 k가 for문 루프의 제일 밖에 위치해야 한다는 것만 잊지 말자.
구현 (Python)
def floyd_warshall():
graph = [[INF]*(n+1) for _ in range(n+1)]
# graph 상태 집어넣는 코드 추가
for k in range(1, V+1): # 중간
graph[k][k] = 0 # 📌 거쳐가는 자기 자신에 대해 0으로 초기화
for i in range(1, V+1): # 시작
for j in range(1, V+1): # 끝
graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])시간복잡도
O(V^3) (V: 노드 수)
3. 벨만-포드 (Bellman-Ford) 알고리즘
다익스트라 알고리즘이 음의 가중치 문제를 해결할 수 없다는 것에서 착안된 알고리즘이다.
음의 가중치가 있는 상태에서 일부 경로에 사이클이 생긴 경우,
해당 경로가 무한히 작아질 가능성이 생긴다.
따라서 음의 가중치 사이클을 캐치하기 위해 사용하는 것이 벨만-포드 알고리즘이다.
작동 원리
노드의 개수를 v개라고 하면 기준 노드로부터 모든 노드를 방문하는 반복을 v-1회 수행하고,
마지막 v번째 반복을 한 번 더 수행했을 때 v-1회 수행 시의 테이블과 값이 달라진다면 음의 사이클이 존재하는 것이라 판단할 수 있게 된다.
음의 사이클이 존재하는 경우 반복을 거듭하게 되면 그 값이 무한히 작아질 것이기 때문이다.
구현 (Python)
def bellman_ford(start):
INF = float('inf')
dp = [INF] * (n+1) # n은 전체 노드 수
dp[start] = 0
for i in range(n):
for s, e, c in graph:
C = dp[s] + c
if dp[s] != INF and dp[e] > C:
dp[e] = C
if i == n-1: # V번째 사이클 수행 시 값이 변경된 경우
return False # 음의 사이클이 존재하는 것으로 보고 False 리턴
return True # 사이클이 존재하지 않으므로 True 리턴여기서 dp[s] 의 INF 유무를 검사하는 이유가 궁금할 수 있는데,
해당 노드가 INF가 아닌 경우 그 노드가 도착점(e)이었던 적이 있다는,
즉 그 노드로 가는 경로가 앞에 있었다는 것을 의미하기 때문이다.
이 알고리즘을 그대로 적용할 수 있는 문제로는 BOJ의 타임머신 문제가 있다.
시간복잡도
O(VE) (V: 노드 수, E: 간선 수)
