Shortest Paths 문서 원본 보기

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

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

==Applications for Shortest Paths==
그래프 상 두 노드 간 최단 경로를 찾는 문제는 실제 여러 분야에서 나타나며, 아래와 같다:
* 교통 문제(Transportation problems): 두 지점 사이의 가장 저렴하거나 빠른 이동 경로를 찾는 문제
* 이동 계획(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>

==각주==