Shortest Paths

개요

해당 문서에서는 그래프에서의 최단 경로(shortest path)를 찾는 알고리즘을 설명한다.

Applications for Shortest Paths

그래프 상 두 노드 간 최단 경로를 찾는 문제는 실제 여러 분야에서 나타나며, 아래와 같다:

교통 문제(Transportation problems): 두 지점 사이의 가장 저렴하거나 빠른 이동 경로를 찾는 문제
- 대표적인 사례가 네트워크 라우팅이며, 이는 LS 라우팅 알고리즘 문서에서 자세히 확인할 수 있다.
이동 계획(Motion planning): 로봇이나 캐릭터가 장애물을 피해 이동하는 경로를 구하는 문제.
통신 문제(Communications problems): 두 노드 간 신호 전송이 가장 빠른 경로를 찾는 문제

또한, 자연어 처리에 최단 경로 문제를 응용할 수 있다. 숫자키를 이용하여 문자를 입력하고자 할때, 여러 단어 후보가 생긴다. 예를 들어 4483을 입력한다면 가능한 단어는 “give” 또는 “hive”이다. 이때 각 가능한 단어를 정점(vertex) 으로, 단어 간 가능한 연결 관계를 간선(edge) 으로 표현할 수 있다. 따라서 최단 경로 문제를 활용하여 문장 해석을 하는 것은, 가능한 후보 중 의미적으로 가장 자연스러운 조합(=가장 짧은 경로) 를 찾는 과정이다. 이 과정은 figure 1에 잘 나타나 있다. 이때 그래프에는 간선(단어 간 연결)에 “확률 기반 가중치(weight)”를 부여해야 한다. 이는 두 단어가 문장에서 인접할 확률을 기반으로 한다. 이 경우에는 Dynamic Programming 또는 Viterbi 알고리즘을 사용해 DAG(Directed Acyclic Graph) 내에서 최소 가중치 경로를 찾아야 한다.

Kind of Shortest Paths Problem

최단 경로 문제의 가장 기본적인 형태는 가중치 그래프(weighted graph)에 대한 것이다. 그 이유는 가중치 그래프에 대한 최단 경로가 도로 문제 등 다양한 문제에서 활용될 수 있기 때문이다. 하지만 최단 경로 문제는 그래프의 특성에 따라 여러 가지 고려할 점이 존재하며, 해당 문단에서는 이에 대해 설명한다.

Unweighted Graphs

비가중 그래프(Unweighted Graph)는 모든 간선의 비용이 동일한 그래프를 의미한다. 따라서 비가중 그래프에서의 최단 경로는 가장 적은 간선을 지나는 경로이다. 이는 n개의 정점과 m개의 간선이 주어졌을 때, BFS(Breadth-First Search)로 O(n + m) 시간에 해결 가능하다. 하지만 BFS 그래프를 가중 그래프에 적용할 수는 없는데, 이는 여러 개의 작은 간선을 지나는 게 한 개의 큰 간선을 지나는 것보다 더 저렴할 수 있기 때문이다.

Negative Edge Weights

그래프에 대해 음수 가중치 간선(negative edge) 이 존재하면 문제가 복잡해진다. 이는 “음수 가중치 순환(negative cycle)”이 있으면, 무한히 돌면서 비용을 계속 줄일 수 있어 최단 경로가 정의되지 않기 때문이다. 예를 들어, A → B → C → A 로 돌아오는데 합이 -3이라면 계속 순환할수록 더 짧은 경로가 생기므로 의미 없는 결과가 된다. 따라서 일반적으로는 모든 가중치를 양수라고 설정하며, 특히 Dijkstra는 양수 가중치만 다루는 알고리즘이다. 예외적으로 Bellman-Ford 알고리즘 등은 음수 가중치를 처리할 수 있다. 이때 MST(Minimum Spanning Tree)는 음수 가중치와 상관없으므로 이에 대해 혼동하면 안된다.^[1]

Dijkstra’s Algorithm

다익스트라 알고리즘(Dijkstra’s Algorithm)은 간선의 가중치가 양수인 가중치 그래프에서의 최단 경로를 탐색하는 알고리즘이다. 다익스트라 알고리즘의 핵심 원리는 부분 최적성(Optimal Substructure)이다. 부분 최적성이란, 만약 경로 s→…→x→…→t 가 최단 경로라면, 그 일부인 s→…→x 도 역시 최단 경로여야 한다는 뜻이다. 이를 이용하여 Dynamic Programming 방식으로 접근할 수 있다. 이는 이미 구한 가까운 노드들의 최단 경로 정보를 이용해 점점 멀리 있는 노드들의 최단 경로를 확장해 나가는 구조이다.

How Dijkstra’s Algorithm works

다익스트라 알고리즘의 시작 단계(Initialization)에서는 출발점 s에서 각 노드까지의 거리를 초기화한다. 이는 아래와 같다:

d(s, s) = 0 (자기 자신까지의 거리는 0)
나머지 노드는 무한대로 설정한^[2] 후, 각 정점 s에서 연결된 간선 중 가장 짧은 간선을 이용해 인접 노드의 거리값을 갱신한다.

다익스트라 알고리즘은 시작 단계 이후, 주어진 거리 배열(distance array)를 업데이트(update)하며 최단 경로를 탐색한다. 이는 정점 s에서 어떤 정점 x에 대한 최단 경로가 확정되면, 그 노드와 연결된 모든 간선을 검사해 s→x→y 가 기존 s→y보다 짧은지 확인하고 갱신하는 방식이다. 즉, 거리 배열(distance array)을 유지하면서 새 노드를 확정할 때마다 그 이웃 노드들의 거리값을 업데이트하는 방식이다. 아래는 다익스트라 알고리즘에 대한 수도 코드이다:

//initialize
known = {s}
for i = 1 to n, dist[i] = <math>\infty</math>
for each edge (s, v), dist[v] = d(s, v) //s와 연결된 정점에 대해 dist 업데이트
last = s //마지막으로 확정된 정점

//update
while (last <math>\neq</math> t) //t는 목표 정점
       select v such that dist(v) = min<sub>unknown</sub>(dist(i))
       for each edge (v, x):
           dist[x] = min(dist[x], dist[v] + w(v, x))
       last = v
       known = known <math>\cup</math> {v}

위 수도 코드에서 known 집합은 “최단 경로가 확정된 정점들”을 의미한다. 이때 각 과정에서는 아직 확정되지 않은 노드 중 가장 dist 값이 작은 것을 선택하여 dist값을 확정하며, 선택된 노드의 모든 인접 노드에 대해 거리를 갱신한다. 이 과정을 반복하여 최단 경로를 탐색한다. Figure 2는 다익스트라 알고리즘을 실행한 예시 결과이다.

다익스트라 알고리즘은 Prim 알고리즘과 유사하다. 이는 Prim도 “가장 작은 비용으로 확장하는 구조”를 사용하며, 둘 다 “가장 가까운 정점부터 추가”라는 탐욕적(greedy) 구조를 가지기 때문이다.

각주

↑ MST는 자체 정의에 의해서 사이클을 배제한 트리를 의미하기 때문이다.
↑ 다른 정점에 대한 거리를 모르기 때문이다.

[1] MST는 자체 정의에 의해서 사이클을 배제한 트리를 의미하기 때문이다.

[2] 다른 정점에 대한 거리를 모르기 때문이다.

[1]

[2]