🌊 최단 경로 찾기 알고리즘
🐸 이해하기
최단경로 찾기 알고리즘?
노드 간 가중치가 주어질 때, 시작 노드부터 모든 노드까지의 최소값을 구하는 알고리즘이다.
이해하는데에 큰 어려움은 없었고, 이전 블로그에서 한 번 코드를 아카이빙 한 적 있지만 자꾸 까먹어 아예 각 잡고 정리를 해야겠다 싶었다.
정리하면서 참고한 글은 포스트 최하단에 링크되어있다.
최단 경로를 찾는 문제는 크게 세가지로 나뉜다.
- 특정 노드에서 특정 노드까지의 최단 경로 ⭢ 다익스트라 알고리즘
- 특정 노드에서 모든 노드까지의 최단 경로
- 가중치가 모두 양수인 경우 ⭢ 다익스트라 알고리즘
- 가중치에 음수가 있는 경우 ⭢ 벨만 포드 알고리즘
- 모든 노드에서 모든 노드까지의 최단 경로 ⭢ 플로이드 워셜 알고리즘
즉 저 세개의 알고리즘은 어쨌든 그래프에서 노드 사이에 최단 경로를 찾는 알고리즘임을 알 수 있다.
가끔 MST(최소 스패닝 트리)와 헷갈리곤 하는데, 여기서도 차이점을 구분할 수 있어야한다.
MST와 뭐가 다른가
MST 알고리즘(크루스칼, 프림)은 그래프에서 최소 비용으로 모든 점을 연결하는 알고리즘이다.
그에 비해 최단 경로를 찾는 알고리즘의 경우, 단순히 노드 사이에 가중치 합이 가장 작은 알고리즘을 찾을 뿐이다.
즉 다익스트라 알고리즘을 끝까지 돌린다고해서, 최소 스패닝 트리를 완성할 수는 없다. 두 알고리즘은 목적이 다르다.
1️⃣ 다익스트라 (Dijkstra)
본 포스트에서 다루는 첫 번째 알고리즘이다.
특정 노드와 모든 노드 사이의 최단 거리를 구하며, 가중치가 모두 양수일 때 사용한다. (== 특정 노드와 특정 노드 사이의 최단거리)
단방향과 양방향(사이클) 모두 적용 가능하며, 이는 구현 상에서 약간의 차이가 있을 뿐 나머지는 동일하다.
또한 다익스트라는 그리디 알고리즘의 일부이며, 대개 우선순위 큐를 이용하여 구현한다.
- 시작하기 전, 노드의 개수 + 1 길이의 리스트에 INF를 채운다
- 길이는 노드가 1번부터 시작하기 때문이다.
- 이는 시작 노드부터 특정 노드까지의 가중치 리스트이다. 최소값을 INF로 설정하여 비교하면서 최소값을 찾아낸다.
- 가중치 리스트에서 시작 노드의 값을 0으로 초기화한다.
- 시작노드에서 시작노드까지의 최단 거리는 당연히 0이기 때문이다.
- 시작 노드에 연결된 특정 노드까지의 가중치와, 현재 가중치 리스트에 들어있는 값을 비교한다.
- 만약 시작 노드에서 특정 노드까지의 가중치가 더 짧다면, 가중치 리스트에 해당 값으로 초기화한다.
- 이제 연결된 노드 중, 방문하지 않았으면서 가장 가중치가 작은 노드로 이동한다.
- 3번의 행위를 반복한다.
글로 보면 헷갈릴 수 있으니, 이미지와 코드를 함께 보면 좋다.
구현하기 - 단방향 그래프
# python
import sys, heapq
input = sys.stdin.readline
INF = sys.maxsize
n, m = list(map(int, input().rstrip().split())) # n: 노드 개수 / m: 간선 개수
k = int(input().rstrip()) # 시작 노드
graph = [[] for _ in range(n + 1)] # 1번 노드부터 시작하기 때문에
distance = [INF] * (n + 1)
for _ in range(m):
u, v, m = list(map(int, input().rstrip().split())) # u: 출발 노드 / v: 도착 노드 / m: 가중치
graph[u].append((v, m))
def dijkstra(start): # 시작 노드의 번호를 인자로 받음
q = []
heapq.heappush(q, (0, start)) # (우선순위, 노드)
distance[start] = 0 # 시작 노드의 거리는 0
while q:
dist, now = heapq.heappop(q) # 우선순위가 가장 낮은 노드 == 가장 가까운 노드
if distance[now] < dist: # 이미 방문한 노드임
continue
for node in graph[now]: # 연결된 모든 노드 탐색
if dist + node[1] < distance[node[0]]: # 기록된 거리보다 새로 연결하는게 더 짧다면
distance[node[0]] = dist + node[1] # 해당 노드까지의 거리를 새로 갱신
heapq.heappush(q, (dist + node[1], node[0]))
dijkstra(k) # 인자로 시작 노드 전달
print(distance)
구현하기 - 양방향 그래프
import sys, heapq
input = sys.stdin.readline
INF = sys.maxsize
n, m = list(map(int, input().rstrip().split())) # n: 노드 개수 / m: 간선 개수
k = int(input().rstrip()) # 시작 노드
graph = [[] for _ in range(n + 1)] # 1번 노드부터 시작하기 때문에
distance = [INF] * (n + 1)
for _ in range(m):
u, v, m = list(map(int, input().rstrip().split())) # u: 출발 노드 / v: 도착 노드 / m: 가중치
graph[u].append((v, m))
graph[v].append((u, m)) # 양방향인 경우
def dijkstra(start): # 시작 노드의 번호를 인자로 받음
q = []
heapq.heappush(q, (0, start)) # (우선순위, 노드)
distance[start] = 0 # 시작 노드의 거리는 0
while q:
dist, now = heapq.heappop(q) # 우선순위가 가장 낮은 노드 == 가장 가까운 노드
if distance[now] < dist: # 이미 방문한 노드임
continue
for node in graph[now]: # 연결된 모든 노드 탐색
if dist + node[1] < distance[node[0]]: # 기록된 거리보다 새로 연결하는게 더 짧다면
distance[node[0]] = dist + node[1] # 해당 노드까지의 거리를 새로 갱신
heapq.heappush(q, (dist + node[1], node[0]))
dijkstra(k) # 인자로 시작 노드 전달
print(distance)
사실 두 코드는 다를게 없다.
다른 점이라면 그래프를 초기에 세팅할 때 시작 노드와 도착 노드 양쪽을 바꾸어서 넣어주느냐 안하느냐의 차이정도!
2️⃣ 벨만 포드 (Bellman-Ford)
특정 노드와 모든 노드 사이의 거리를 구할 때 사용하는 알고리즘이다.
다익스트라와 차이가 있다면, 가중치에 음수가 있는 경우에도 사용할 수 있다는 것이다.
반대로 말하자면 다익스트라 알고리즘은 가중치에 음수가 있는 경우에는 사용할 수 없다.
또한 해당 그래프에서 음수인 사이클이 존재하는지 여부도 알 수 있다.
가령 이런식으로 음수 사이클이 생긴다면, 계속 돌기 때문에 최단 거리가 존재하지 않게 된다.
방식은 다익스트라와 유사하나, 몇 가지 다른 점이 있다.
- 다익스트라의 경우, 방문하지 않은 노드 중 가장 가중치가 작은 노드를 선택한다.
- 때문에 음수 가중치가 있는 경우에는 최적해를 탐지하지 못한다.
- 벨만포드의 경우, 모든 노드를 선택하고 검사한다.
- 때문에 음수 가중치가 있는 경우에도 최적해를 탐지할 수 있다.
- 이 과정에서 음수 사이클 또한 알 수 있다.
- 하지만 다익스트라에 비해 시간 복잡도가 높다는 단점이 있다.
음수 사이클을 찾는 방법은 아래와 같다.
총 노드가 n개 있는 경우, n-1 번 동안 전체 간선을 검사한다.
그리고 한 번 더 검사했는데, 값이 갱신된다면 음수 사이클이 존재하는 것이다..
구현하기
import sys
input = sys.stdin.readline
INF = sys.maxsize
n, m = list(map(int, input().rstrip().split())) # n: 노드 개수 / m: 간선 개수
k = int(input().rstrip()) # 시작 노드
graph = []
distance = [INF] * (n + 1)
cycle = False
for _ in range(m):
u, v, m = list(map(int, input().rstrip().split())) # u: 시작 노드 / v: 도착 노드 / m: 가중치
graph.append((u, v, m))
def bellman(start):
global cycle
distance[start] = 0 # 시작노드 가중치 0으로 초기화
for i in range(n):
for u, v, m in graph: # u: 시작 노드 / v: 도착 노드 / m: 가중치
if distance[u] != INF: # 출발 노드가 방문한적 없는 노드면 패스
dist = distance[u] + m
if dist < distance[v]:
if i == n - 1: # 값이 갱신 되었는데, n번째인 경우
cycle = True
distance[v] = dist
bellman(k)
print(cycle, distance)
마찬가지로 양방향 그래프로 만들 수 있으며, 방식은 다익스트라와 동일하다. (포스트에서는 생략한다)
3️⃣ 플로이드 워셜 (Floyd-Warshall)
모든 노드에서 모든 노드로의 최단 거리를 구하는 알고리즘이다.
최단 거리를 구하는 알고리즘 중 최악의 시간 복잡도를 가지지만 가장 쉽다.
총 3중 반복문을 이용하는데, 거치는 점을 중심으로 두 노드를 연결한 값을 비교하여 갱신한다.
구현하기
import sys
input = sys.stdin.readline
INF = sys.maxsize
n, m = list(map(int, input().rstrip().split())) # n: 노드 개수 / m: 간선 개수
k = int(input().rstrip()) # 시작 노드
distance = [[INF] * n for _ in range(n + 1)]
for _ in range(m):
u, v, m = list(map(int, input().rstrip().split())) # u: 시작 노드 / v: 도착 노드 / m: 가중치
distance[u][v] = min(distance[u][v], m)
def floyd():
for k in range(n): # 거치는 노드
for i in range(n): # 시작 노드
for j in range(n): # 끝 노드
if i == j:
distance[i][j] = 0
continue
distance[i][j] = min(distance[i][k] + distance[k][j], distance[i][j])
floyd()
for row in distance:
for el in row:
if el >= INF: print(0, end=' ')
else: print(el, end=' ')
print()
참고
다익스트라 알고리즘 with python
다익스트라 알고리즘은 최단거리를 구하는 알고리즘입니다. 다익스트라 알고리즘을 사용하면, 하나의 노드에서 다른 모든 노드까지의 거리를 구할 수 있습니다. 개인적으로 개념을 이해하는
velog.io
최단 경로 알고리즘 - 다익스트라 알고리즘 (Dijkstra Algorithm)
최단 경로 알고리즘 주어진 노드(node)와 간선(edge)들 중, 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 문제는 아래와 같이 3가지로 주어질 수 있다. 1. 특정 노드에서 시작해 특정 노드까지 도
jainn.tistory.com
[Algorithm] 벨만-포드 알고리즘(Bellman-Ford algorithm) - Python
벨만-포드 알고리즘을 통해 그래프에서 최단 거리를 구하고, 음수 사이클 존재 여부를 판단하는 방법을 알아보자.
velog.io