지난번에 못다룬, 그래프 알고리즘 중 최단경로를 탐색하는 알고리즘에 대해 알아보도록 하겠다.
heap = [(0,1)]
heap = [(0,1)] -> pop 1 -> push 2,3 -> heap = [(3,2),(4,3)]
heap = [(3,2),(4,3)] -> pop 2 -> push 4,6 -> heap = [(4,3),(12,6),(13,4)]
heap = [(4,3),(12,6),(13,4)] -> pop 3 -> push 4,5 -> heap = [(9,5),(12,6),(12,4),(13,4)]
(12,4)
를 먼저 빼서 값들을 갱신한 다음에, 그 이후에 나올 (13,4)
는 무시한다.1번 -> 8번으로 가는 최단거리는 14이고, 8번부터 부모노드를 타고 쭉 타고 올라오면
8<-6<-2<-1
라는 경로를 얻을 수 있다.
다익스트라 알고리즘은 힙을 사용해서 구현한다.
import heapq
n = {노드의 개수}
INF = 1e8
distance = [INF] * (n+1) # 최단거리 테이블
graph[출발노드] = [(도착노드, 연결된 간선의 가중치), ...]
def dijkstra(start):
q = []
heapq.heappush(q, (0, start)) # (최단거리, 노드번호)
distance[start] = 0 # 시작노드는 최단거리 0
while q:
dist, now = heapq.heappop(q) # 최단거리가 가장 짧은 노드부터 나온다.
if distance[now] < dist: # 최단거리 테이블에 있는 값이 지금 볼 값보다 작으면 볼 필요 X
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])) # 다음 계산을 위해 큐에 삽입
➕) 2023-08-20 추가 : 쓸 일 없을 줄 알고 대충 넘어갔다가 백준에 딱 잡혀서 정리하러 다시 돌아옴
O(VE)
로 다익스트라(O(ElogV)
)보다는 느리지만 음수 간선이 있어도 최단거리를 찾을 수 있고, 똑같이 음수 간선이 있어도 최단거리를 찾을 수 있는 알고리즘인 플로이드 워셜(O(V^3)
)보다는 시간복잡도가 짧다.V(정점의 개수) - 1
번 반복한다.V
번째 반복차례에) 최단거리 테이블이 갱신된다면 음수사이클이 존재하는 것이다.모든 노드 간의 최단거리를 서서히 완화시켜가면서 실제 최단거리를 구하는 방식이다.
V-1
번 반복하는 이유가장 의문이었던 점은 4번에서 왜 모든 간선을 확인하는 과정을 V-1
번 반복해야 하냐는 것이었다. 인터넷을 찾아보면 다 정점 V
개를 지닌 그래프에 음수 사이클이 없을때, 최단경로는 한 정점을 2번 지나는 일이 없으며, 최단경로는 간선을 최대 V-1
개만을 가지기 때문이라고 한다.
근데 그거랑 이거랑 뭔 상관?? 우선 예시를 보자. (아래 예시는 모두 코드 상에서의 동작예시임)
아래와 같은 그래프가 있고, 시작점 1번 노드부터 가장 먼 4번 노드까지의 최단경로를 찾는다고 가정해보자. 간선 확인 순서는 가장 최악의 상황을 가정하기 위해 C->B->A 순서대로 확인한다고 하자.
첫번째 반복에서 C와 B는 각 간선의 시작점이 아직 INF이기 때문에 갱신하지 않는다. A 간선에서만 업데이트를 진행한다.
두번째 반복에서는 첫번째 반복에서 노드2까지의 거리가 갱신되었으므로, B를 확인할때 이전에 못했던 갱신을 할 수 있다. C는 아직도 갱신할 수 없는 상태다.
세번째 반복차례가 돼서야 비로소 C를 사용하는 경로를 갱신할 수 있게 된다. 정점의 개수가 4개이므로, 이번 반복이 마지막이다.
음수 간선 확인을 위해 한번 더 반복문을 돌려보자. 이 예시는 음수사이클이 없으므로, 네번째 반복에서는 최단거리 테이블이 갱신되는 부분이 하나도 없다.
이 경우에는 노드가 4개이기 때문에 최단경로는 최대 3개의 간선을 가질 수 있었고, 이에 따라 반복문을 3번 수행했을 때 실제 최단경로를 구할 수 있었다. 여기서 노드가 V
개일때 최단경로를 구하려면 간선 확인을 최소 V-1
번 반복해야한다는 것을 유추해낼 수 있다.
그런데 만약에 운이 좋아서 간선 확인을 A->B->C 순으로 했으면 어떻게 될까?
첫번째 반복에서 이미 답이 구해져버리고, 두번째부터 V-1
번째까지 아무런 의미 없는 반복문이 이어진다. 이럴 경우 이후 반복문은 실행하지 않아도 된다.
그럼 아까 말한 V-1
번 반복은 어디다 팔아먹은걸까?? 조금 이따 알아보도록 하자.
또다른 가정으로, 만약에 음수 사이클이 있었다면 어땠을까?
음수 사이클이 있을때는 4번째 반복차례에도 최단거리 테이블이 갱신되고 있는 것을 볼 수 있다. 이 부분에 착안해서 음수사이클의 존재를 찾아내는 것이다.
알고리즘 설명과 코드가 일치하지 않는 부분이 있어서 거기서 엄청나게 혼동이 온 것 같다.
혼란하다 혼란해!
더 찾아보니 k
번째 루프는 시작점으로부터 k
개의 간선을 거쳐 도달할 수 있는 최단경로를 모두 갱신해주는 것이라고 하는데, 이를 중점으로 다시 생각해보겠다.
아까 다시 보기로 했던 예시2같은 경우에, (그림 그리기 귀찮ㅜ)
코드 ver.
알고리즘 설명 ver.
그래서 알고리즘상으론 최단경로는 최대 V-1
개의 간선을 가지기 때문에 V-1
번의 루프를 돌려야하는데, 코드에서는 간선 방문 순서에 따라 더 빨리 끝날 수도 있는거다. 운이 나빠서 최악의 경우였어도 최대 V-1
번만 반복하면 무조건 최단거리가 나온다는 것이 보장되기 때문에 코드에서도 V-1
번 돌리는 거다.
(틀렸을수는 있음..)
INF = int(1e9)
V, E = map(int, input().split())
edges = []
distance = [INF] * (V + 1)
for _ in range(E):
s, d, w = map(int, input().split())
edges.append((s, d, w)) # edges = [(시작점, 도착점, 비용),...]
def bellman-ford(start):
# 시작점은 0, 나머지는 INF
distance[start] = 0
# 최단거리 갱신 V-1번 + 음수사이클 판별용 1번 = 총 V번 반복
for i in range(V):
# 모든 간선들 확인 (순서 무관)
for s, d, w in edges:
# 이미 방문한 시작점 & 도착점까지의 거리보다 시작점까지의 거리 + 비용이 더 작을때
if distance[s] != INF and distance[d] > distance[s] + w:
# 최단거리 갱신
distance[d] = distance[s] + w
# 최단거리 갱신했는데 사실 이게 V-1번째 반복이었다면?
if i == V - 1:
# 음수 사이클 발생
return True
return False
negative_cycle = bellman-ford(1)
if negative_cycle:
print("음수 사이클 발생")
else:
for i in range(2, V+1):
if distance[i] == INF:
print("도달할 수 없음")
else:
print(distance[i])
플로이드 워셜 알고리즘의 점화식
최단거리테이블[from][to] = weight
형태로 저장한다.1번 -> 3번으로 가는 최단거리는 8이다.
# n = 노드의 개수
def Floyd_Warshall():
distance = [[INF] * n for _ in range(n)]
# ~ 최단경로 테이블 초기화 과정은 생략 ~
for k in range(n):
for a in range(n):
for b in range(n):
distance[a][b] = min(distance[a][b], distance[a][k] + distance[k][b])