✅ 최단 경로 알고리즘
: 가중치가 없는 그래프에선 가장 적은 edge 개수를 의미하고 가중치가 존재하는 그래프에선 두 node를 연결하는 edge가 가진 weight의 합이 최소가 되도록 해야 한다.
그렇다면 이전의 학습한 DFS, BFS를 최단 경로 문제에 적용할 수 있을까?
- DFS는 최단경로 탐색 문제에 있어 효율적이지 않다.
모든 노드들이 시작점으로 고려되어야 하는 문제가 있어 시간복잡도가 O(n^2)이 되어 비효율적이다. 반면, BFS는 O(n+v)의 복잡도를 가져 DFS보다 효율성을 띈다. 이외에도 stack을 사용하는 DFS에 비해 BFS는 deque를 사용하므로 비교적 stack overflow문제에서 자유롭게 공간을 활용할 수 있어 더 넓은 범위를 탐색할 수 있다.
- 가중치가 있는 그래프에서 BFS, DFS 그대로 사용할 수 없다
DFS를 활용하면 전체 node를 통해 edge를 탐색하여 경로를 고려하므로 (노드가 n개라면 경로의 수는 n!으로 기하급수적으로 늘어나게 되어) 효율성이 떨어지게 된다.
BFS를 활용하면, Depth 기준으로 탐색을 진행하는 BFS 특성에 따라 weight를 고려하지 않고 최단 경로를 찾게 된다. 또한 Greedy 알고리즘이 아니기에 BFS는 최단경로 알고리즘으로써 사용될 수 없다.
위와 같은 이유로 최단 경로 알고리즘인 Dijkstra가 등장했다.
✍️ 다익스트라 (Dijkstra)
- 특정 노드에서 출발해 다른 노드로 가는 모든 최단 경로를 구하는 알고리즘
- 0보다 작은 값을 갖는 음의 가중치가 없어야 정상적으로 작동 (+ BFS 기반)
- 매번 가장 weight가 적은 노드의 선택을 반복하므로 Greedy alorithms이라 할 수 있다.
- stack이 아닌 heapq를 사용하면 O(v^) 에서 O(ElogN)로 줄어들고 현 시점 짧은 edge 선택
- 각 노드까지 거리를 list자료 구조로 memoization하여 더 짧은 경로로 업데이트 진행
다익스트라 알고리즘 동작과정은 다음과 같다
1. 시작 노드 지정
2. 최단 거리 초기화
3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택
4. 해당 노드 거쳐 다른 노드를 가는 비용 계산해 최단 거리 업데이트
5. 3~4 과정 반복
코드로 기초적인 Dijkstra 알고리즘을 보면 다음과 같다.
import heapq
graph = [[] for _ in range(nodes+1)]
for _ in range():
graph[u].append((v, w))
# 시작노드로 부터 거리 값 저장하는 dist 리스트 생성
dist = [1e9] * (nodes+1)
def dijkstra(graph, start_node):
dist[start_node] = 0
queue = []
# queue에 시작노드의 거리와 노드 저장
heapq.heappush(queue, [dist[start_node], start_node])
# queue에 노드가 없을 때까지 반복
while queue:
# 탐색할 인접노드, 거리 가져오기
adj_dist, adj_node = heapq.heappop(queue)
# 다음 노드 이동거리가 현재보다 멀면, 가지치기
if dist[adj_node] < adj_dist:
continue
for next_node in graph[adj_node]:
# 노드 지날 때마다 거리 업데이트
cost = adj_dist + next_node[1]
# 거리 값이 더 작다면
if cost < dist[next_node[0]]:
# 최단 거리 갱신
dist[next_node[0]] = cost
다음 인접 노드와의 거리 계산 위해 큐에 삽입
heapq.heappush(queue, [cost, next_node[0])한계점
- weight가 음수인 것이 존재한다면 모든 경우의 수를 다 따져야 하므로 greedy 알고리즘인 다익스트라로 정상적인 알고리즘 작동 X
✍️ 벨만 포드 (Bellman-Ford)
- 다익스트라의 음수 가중치로 인해 최단 경로가 정의되지 않는 문제를 보완.
- 시작노드~각 노드로 가는 최단 거리의 상한을 적당히 예측 후 오차를 반복적으로 줄이는 방식
- 모든 edge를 확인하며 최단 거리를 찾기에 느림
- 수행과정에서 각 노드까지의 최단거리 상한을 담은 list인 upper[]를 유지하고 알고리즘 진행됨에 따라 값이 줄어 결과적으로 실제 최단 거리만 남게 된다.
- edge relaxation 수행 : node가 지난온 간선의 가중치들을 방문했던 모든 edge에 더해줌
- O(N*E)의 시간복잡도
벨만 포드 알고리즘의 동작과정은 다음과 같다.
1. 시작점 제외하고 그래프 구조를 모르므로 시작점은 0, 나머지는 양의 무한대로 초기화
2. 모든 간선을 통과하며 edge relaxation 반복하여 최단거리 순차적으로 갱신
코드로 기초적인 Bellman-Ford 알고리즘을 보면 다음과 같다.
graph = []
for _ in range(간선수):
u, v, w = map(int, input().split())
graph.append((u, v, w))
dist = [INF] * (n+1)
def bellmanford(start_node):
# 시작점 초기화
dist[start_node] = 0
# 노드수 만큼 edge relaxation 반복, 노드수-1만큼 탐색 후 마지막은 음수사이클 확인
for i in range(노드수):
# 반복할 때마다 모든 간선 확인
for j in range(간선수):
cur_node, next_node, cost = graph[j]
# 현재 간선 거쳐 다른 노드 이동 거리가 더 짧다면
if dist[cur_node] != INF and dist[cur_node] + cost < dist[next_node]:
dist[next_node] = cost + dist[cur_node]
# v번째 반복에서 갱신되는 값 있으면 Negative Cycle 존재
if i == 노드수 - 1:
return False
return True✍️ 플로이드-워셜 (Floyd-Warshall)
- 앞서 학습한 알고리즘과 달리 플로이드-워셜은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 문제이다.
- 다익스트라와 마찬가지로 단계 별 거쳐가는 정점을 기준으로 알고리즘을 수행한다.
(다만 매 단계마다 방문 안한 노드 중에 최단 거리를 찾는 과정 필요 X)- 2차원 리스트에 최단 거리 정보 저장
- 기본적으로 DP 기술에 의거한다.
- 시간 복잡도 : 3중 for문 O(v^3)
- 공간 복잡도 : 2차원리스트 O(v^2)
플로이드 워셜 알고리즘의 동작과정은 다음과 같다.
1. 연결된 간선은 값을 채우고 연결안된 경우 무한으로 초기화, 자신은 0으로 그래프 생성
2. A > B로 가는 비용과 A>K>B의 비용을 비교해 더 작은 값으로 갱신
3. 2번 반복
코드로 기초적인 Bellman-Ford 알고리즘을 보면 다음과 같다.
# n : 노드수, e : 간선수
graph = [[0 if i == j else 1e9 for i in range(n+1)] for j in range(n+1)]
for _ in range(e)
u, v, w = map(int, input().split())
graph[u][v] = w
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])
for a in range(1, n + 1):
for b in range(1, n + 1):
if graph[a][b] == 1e9:
print('Infinity', end = ' ')
else:
print(graph[a][b], end = ' ')
print()✅ MST (Minimum Spanning Tree)
MST이전, Spanning tree(신장 트리)를 알아보고 시작하자.
🎈 spanning tree (최소 연결 부분 그래프)
- 그래프 내 모든 정점 포함하는 트리, 즉 그래프 내 일부 간선만 택한 트리
- 한 그래프에는 여러 개의 신장 트리가 존재할 수 있다.
- 모든 노드가 연결되어야 하고 사이클은 포함해선 안된다. N개 노드, N-1개 간선
✅ MST (최소 신장 트리)
ST중 사용된 Edge의 weight 합이 최소인 트리
네트워크에 있는 모든 노드를 가장 적은 수의 간선과 비용으로 연결하는 것
- edge의 weight합이 최소여야 한다.
- n개의 노드를 가진 그래프는 n-1개의 간선만을 사용해야 한다.
- 사이클이 포함되선 안된다.
ex) 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하는 경우
✍️ 크루스칼 (Kruskal)
- Greedy 방법을 이용해 네트워크의 모든 정점을 최소 비용으로 연결해 최적 해답을 구하는 것
- Sparse graph(edge위주), 간선 선택을 기반으로 하는 알고리즘
- 이전 단계에서 만든 신장트리와 상관없이 무조건 최소 간선만 선택하는 방법
- 간선을 가중치 기준 오름차순 정렬 후 추가
- 간선을 기준으로 추가하기에 사이클 여부 확인 必
- union-find 알고리즘 이용 시 간선 e개를 퀵 정렬과 같이 정렬 시 시간복잡도는 O(eloge)
크루스칼 알고리즘의 동작과정은 다음과 같다.
1. 그래프 내 edge들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클 형성 안하는 간선 선택
(낮은 가중치 먼저 선택, 사이클 형성하는 간선 제외)
3. 해당 간선을 현재의 MST 집합에 추가한다.
(집합에 추가할 때 사이클 생성여부 확인해야 한다. (union - find 사용)
코드로 기초적인 Kruskal 알고리즘을 보면 다음과 같다.
# v : 노드 수, e : 간선 수
parent = list(range(v+1))
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
edges = []
total_cost = 0
for _ in range(e):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
edges.sort()
for i in range(e):
cost, a, b = edges[i]
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
total_cost += cost
✍️ 프림 (Prim)
- 시작 정점 기준 연결된 edge 중 가중치가 가장 작은 edge와 연결된 node 추가 후 반복
- 힙큐 사용 (노드 기반 알고리즘), 간선 많은 그래프 (Dense graph)
- 이전 단계에서 만들어진 신장 트리를 확장하는 방법
- 시간 복잡도는 O(elogv)
프림 알고리즘의 동작 과정은 다음과 같다.
1. 시작 정점만이 MST 집합에 포함된다
2. 이전 단계에서 만들어진 MST 집합에 인접 노드 중 최소 간선으로 연결된 노드를 선택해 트리를 확장한다 (가장 낮은 가중치를 먼저 선택)
3. 위 과정을 트리가 N-1개 간선 가질 때까지 반복
코드로 기초적인 Prim 알고리즘을 보면 다음과 같다.
import heapq
import collections
import sys
sys.setrecursionlimit(10**6)
v : 노드 수, e : 간선 수
graph = collections.defaultdict(list)
visited = [0] * (v+1)
for _ in range(e):
u, v, w = map(int, input().split())
graph[u].append([w, u, v])
graph[v].append([w, v, u])
def prim(graph, start):
visited[start] = 1
candidate = graph[start]
heapq.heapify(candidate)
mst = []
total = 0
while candidate:
cost, u, v = heapq.heappop(candidate)
if visited[v] == 0:
visited[v] = 1
mst.append((u, v))
total += cost
for edge in graph[v]:
if visited[edge[2]] == 0:
heapq.heappush(candidate, edge)
return total✅ 위상정렬 (Topological sort)
- 유향 그래프
- 그래프 내 cycle X
- BFS 통해 구현 가능
from collections import deque # v : 노드 수, e : 간선 수 v, e = map(int, input().split()) indegree = [0] * (v + 1) graph = [[] for _ in range(v + 1)] for _ in range(e): a, b = map(int, input().split()) graph[a].append(b) indegree[b] += 1 def topological_sort(): result = [] q = deque() for i in range(1, v + 1): if indegree[i] == 0: q.append(i) while q: cur = q.popleft() result.append(cur) for g in graph[cur]: indegree[g] -= 1 if indegree[g] == 0: q.append(g) for i in result: print(i, end=' ') topological_sort()
