1. 최단 경로의 이해
먼저 최단 경로의 기본 성질에 대해 파악해보자.
- u → v : 노드 u에서 노드 v로의 하나의 엣지로 구성된 경로
- s ⇝ v : 노드 s에서 v로의 경로를 표 시하고, 중간에 여러 노드가 존재 가능
- s ⇝ u → v 인 경우, 이 경로에서 u는 v의 predecessor 또는 parent이다
- 만약 s ⇝ u → v 가 s에서 v로의 최단 경로 중 하나라면, s ⇝ u 역시 s에서 u까지의 최단 경로 중 하나이다.
s에서 v까지의 여러 경로 중에서 u를 통해 v에 도달하는 경로중에 최단 경로가 있다는 의미이고, s ⇝ u를 먼저 계 산하여 알고 있다면, s ⇝ u → v는 쉽게 계산할 수 있다.
dist[v] = "s에서 v까지의 최단 경로의 길이"라고 정의하면 다음과 같은 식이 성립한다.
즉, v로 들어오는 각 에지 (u, v)에 대해서 dist[u] + weight(u → v)를 계산하고 그 중에서 최솟값이 dist[v]가 된다.
결국 dist[v]를 구하기 위해선, dist[v] 계산 전에 dist[u]가 먼저 계산되면 된다. 즉, v의 predecessor인 u에 대해서 dist[u]를 먼저 계산하면 된다. 이런 논리를 계속 적용해나가면, 출발 노드인 s까지 거슬러 올라가게 된다.
당연히 dist[s] = 0이고, s가 아닌 노드 v에 대해선 dist[v] = ∞ 로 초기값을 갖는다.
위와 같은 작업을 간선 완화(edge relaxtion)이라고 한다.
2. 벨만-포드 알고리즘이란? (Bellman-Ford Algorithm)
벨만-포드 알고리즘은 이러한 간선 완화를 모든 엣지(E)에 대해서 총 V-1번 수행하면서 최단 경로를 도출하는 알고리즘이다.
왜 E * (V-1)번인가?
노드가 V개 존재하면 최단 경로는 최대 V-1개 존재할 수 있으며, 매 라운드마다 모든 엣지에 대해서 relaxtion이 일어나는 과정에서 순차적으로 각 노드간의 최단 경로가 도출되기 때문이다. → E * (V-1)
벨만-포드 알고리즘은 다음과 같은 특징을 지니고 있다.
- 간선 완화를 V-1번 수행함으로써 O(VE)의 실행시간을 가지기 때문에 느리다.
- 엣지(Edge)에 가중치가 주어진 방향 그래프를 대상으로 한다. 이때 음수인 가중치 또한 처리할 수 있다 -> 느림에도 불구하고 사용하는 이유!
- 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 문제를 다룬다(Single Source Shortest Path Problem).
- 음수 사이클이 존재한다면 최단 경로를 보장할 수는 없다. 하지만 음수 사이클이 존재한다는 사실은 발견할 수 있다.
어떻게 음수 사이클을 발견할 수 있는가?
최단 경로를 구하는 과정(round)이 모두 끝난 후에 relaxtion이 발생한다면, 그것은 음수 사이클이 존재하는 것이다.
음수 사이클에 속하는 경로의 가중치는 음수이기 때문에 당연하게 계속해서 relaxtion이 발생할 수 밖에 없다.음수 사이클에 대한 설명은 여기에서 확인할 수 있다.
3. 슈도 코드 및 실제 구현(Python)
슈도 코드
BellmanFord(G,w,s):
//초기화 과정
for each u in G.V: //노드를 초기화 하기
distance[v] = inf //모든 노드의 최단거리를 무한으로 지정
parent[v] = null //모든 노드의 부모 노드를 널값으로 지정
distance[s] = 0 //출발점의 최단거리는 0으로 지정한다
//거리측정 과정
for i from 1 to len(G.V): //노드의 숫자만큼
for each (u,v) in G.E: //모든 변을 체크해 최단 거리를 찾아본다.
if distance[u] + w[(u,v)] < distance[v]:
//만약 u를 경유하여 v로 가는 거리가 현재 v의 최단 거리보다 짧으면
distance[v] = distance[u] + w[(u,v)] //그 거리를 v의 최단거리로 지정
parent[v] = u //u를 v의 부모 노드로 지정
//음수 사이클 체크 과정
for each (u,v) in G.E:
if distance[u] + w[(u,v)] < distance[v]:
return false //음수 사이클을 확인하고 알고리즘을 정지
return distance[], parent[]실제 구현
...
graph = collections.defaultdict(list)
for u, v, w in inputs: # 양방향 그래프라고 가정
graph[u].append([v, w])
graph[v].append([u, w])
def bellman_ford(s):
dist = [INF] * (V+1) # V는 노드의 개수
dist[s] = 0 # 시작 노드의 거리는 0으로 설정
for _ in range(V-1):
for u in range(1, V+1):
for v, c in graph[u]:
if dist[v] > dist[u] + c:
dist[v] = dist[u] + c
for u in range(1, V+1): # 음수 사이클이 존재하는지 체크
for v, c in graph[u]:
if dist[v] > dist[u] + c:
return False
return dist
4. 다익스트라 알고리즘이란? (Dijkstra Algorithm)
다익스트라 알고리즘은 그리디 알고리즘을 적용하여 벨만-포드 알고리즘에 비해서 간선 완화를 더욱 효율적으로 실행하는 최단 경로 알고리즘이다.
다음과 같은 특징을 지니고 있다.
- 엣지(Edge)에 양수 가중치가 주어진 방향 그래프를 대상으로 한다.
- 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 문제를 다룬다(Single Source Shortest Path Problem).
- 다익스트라 알고리즘 초기의 구현에선 시간 복잡도가 O(V^2)였으나 현재에 이르러 우선순위 큐를 적용하면서 O((V+E) log V)가 되었다. 이는 벨만포드 알고리즘에 비해서 빠르다.
5. 슈도 코드 및 실제 구현(Python)
슈도 코드
function Dijkstra(Graph, source)
create vertex set
for each vertex v in Graph: // 초기화
dist[v] ← INFINITY // 소스에서 v까지의 아직 모르는 길이
prev[v] ← UNDEFINED // 소스에서 최적 경로의 이전 꼭짓점
add v to Q // 모든 노드는 초기에 Q에 속해있다 (미방문 집합)
dist[source] ← 0 // 소스에서 소스까지의 길
while Q is not empty:
u ← vertex in Q with min dist[u] // 최소 거리를 갖는 꼭짓점을 가장 먼저 선택한다
remove u from Q
for each neighbor v of u: // v는 여전히 Q에 있다.
alt ← dist[u] + length(u, v)
if alt < dist[v]: // v 까지의 더 짧은 경로를 찾았을 때
dist[v] ← alt
prev[v] ← u
return dist[], prev[]우선순위 큐를 적용한 슈도 코드
function Dijkstra(Graph, source):
dist[source] ← 0 // 초기화
create vertex set Q
for each vertex v in Graph:
if v ≠ source
dist[v] ← INFINITY // 소스에서 v까지의 아직 모르는 길이
prev[v] ← UNDEFINED // v의 이전 노드
Q.add_with_priority(v, dist[v])
while Q is not empty: // 메인 루프
u ← Q.extract_min() // 최고의 꼭짓점을 제거하고 반환한다
for each neighbor v of u: // Q에 여전히 남아 있는 v에 대해서만
alt ← dist[u] + length(u, v)
if alt < dist[v]
dist[v] ← alt
prev[v] ← u
Q.decrease_priority(v, alt)
return dist, prev
파이썬은 아주 친절하게도 우선순위 큐를 최소 힙으로 구현한 heapq 모듈을 제공한다.
이를 이용하여 손쉽게 다익스트라 알고리즘을 구현할 수 있다.
그래프는 defaultdict를 이용해 인접 리스트로 구현했으며, 양방향 그래프라고 가정했다.
실제 구현
...
graph = collections.defaultdict(list)
for u, v, w in inputs: # 양방향 그래프라고 가정
graph[u].append([v, w])
graph[v].append([u, w])
def Dijkstra(start):
dist = [float('inf')] * (V+1) # V는 노드의 개수
dist[start] = 0 # 시작 노드의 거리는 0으로 설정
Q = []
Q.append([dist[start], start])
while Q:
v = heapq.heappop(Q)[1]
for u, w in graph[u]: # edge = (vertex, weight)
if dist[u] > dist[v] + w:
dist[u] = dist[v] + w
heapq.heappush(Q,[dist[u], u])
return dist
heapq 모듈은 sort() 메소드와 유사하게 큐에 담긴 값이 iterable하다면 해당 값의 첫번째 원소를 기준으로 힙연산을 수행한다. 따라서 구현 시 최단 경로의 길이(dist)를 첫 번째 원소로 두어야 함에 유의한다.
또한, 앞서 언급했듯이 다익스트라 알고리즘은 양수 가중치가 주어진 방향 그래프만을 다루기 때문에 만약 문제에서 가중치가 음수로 주어졌다면 벨만-포드(Bellman-Ford) 알고리즘과 같은 다른 알고리즘을 사용해야 한다.
유튜브 강의
참고
Data Structures with Python(신찬수 저)
파이썬 알고리즘 인터뷰(박상길 저)
나무위키
wikipedia
'CS > 알고리즘 이론' 카테고리의 다른 글
| [알고리즘] 이진 탐색(Binary Search) (0) | 2021.06.21 |
|---|---|
| [알고리즘] 그래프 순회(Graph Traversal) (0) | 2021.02.07 |
| [알고리즘] 동적 계획법(Dynamic Programming) (0) | 2021.02.01 |
