Shortest Paths 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]] 

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

==Applications for Shortest Paths==
그래프 상 두 노드 간 최단 경로를 찾는 문제는 실제 여러 분야에서 나타나며, 아래와 같다:
* 교통 문제(Transportation problems): 두 지점 사이의 가장 저렴하거나 빠른 이동 경로를 찾는 문제
** 대표적인 사례가 네트워크 라우팅이며, 이는 [[Routing Algorithms#LS routing algorithm|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|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)는 음수 가중치와 상관없으므로 이에 대해 혼동하면 안된다.<ref>MST는 자체 정의에 의해서 사이클을 배제한 트리를 의미하기 때문이다.</ref>

==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)
# 나머지 노드는 무한대로 설정한<ref>다른 정점에 대한 거리를 모르기 때문이다.</ref> 후, 각 정점 s에서 연결된 간선 중 가장 짧은 간선을 이용해 인접 노드의 거리값을 갱신한다.
다익스트라 알고리즘은 시작 단계 이후, 주어진 거리 배열(distance array)를 업데이트(update)하며 최단 경로를 탐색한다. 이는 정점 s에서 어떤 정점 x에 대한 최단 경로가 확정되면, 그 노드와 연결된 모든 간선을 검사해 s→x→y 가 기존 s→y보다 짧은지 확인하고 갱신하는 방식이다. 즉, 거리 배열(distance array)을 유지하면서 새 노드를 확정할 때마다 그 이웃 노드들의 거리값을 업데이트하는 방식이다. 아래는 다익스트라 알고리즘에 대한 수도 코드이다:
<syntaxhighlight lang="go">
//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}
</syntaxhighlight>
위 수도 코드에서 known 집합은 “최단 경로가 확정된 정점들”을 의미한다. 이때 각 과정에서는 아직 확정되지 않은 노드 중 가장 dist 값이 작은 것을 선택하여 dist값을 확정하며, 선택된 노드의 모든 인접 노드에 대해 거리를 갱신한다. 이 과정을 반복하여 최단 경로를 탐색한다. Figure 2는 다익스트라 알고리즘을 실행한 예시 결과이다.

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

==각주==