Shortest Paths

상위 문서: 알고리즘 설계와 분석

개요

해당 문서에서는 그래프에서의 최단 경로(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(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)는 음수 가중치와 상관없으므로 이에 대해 혼동하면 안된다.