최단 경로 문제 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''최단 경로 문제'''란 가장 짧은 경로에서 두 꼭짓점을 찾는 문제로서, [[가중 그래프]]에서는 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제이다. 예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 이 때, 각 도로 구간에서 걸리는 시간을 변의 가중치라 할 수 있다.

보통은 주어진 가중 그래프에서 (''V''는 꼭짓점, ''E''는 변, 가중치 함수 ''f''&nbsp;: ''E''&nbsp;→&nbsp;'''R''') <math>\sum_{p\in P} f(p)</math>가 v에서 v'로 가는 모든 경로들 중 최소가 되도록 하는 경로를 찾는 문제이다.
이런 문제는 '''단일-쌍 최단 경로 문제'''라고 부르며, 아래의 일반화된 문제들과는 차이가 있다.

* '''단일-출발 최단 경로 문제''' : 단일 꼭짓점 ''v''에서 출발하여 그래프 내의 모든 다른 꼭짓점들에 도착하는 가장 짧은 경로를 찾는 문제이다.
* '''단일-도착 최단 경로 문제''' : 모든 꼭짓점들로부터 출발하여 그래프 내의 한 단일 꼭짓점 ''v''로 도착하는 가장 짧은 경로를 찾는 문제이다. 이 문제에서 그래프 내의 꼭짓점들을 거꾸로 뒤집으면 출발 최단 경로 문제로 바뀔 수 있다.
* '''전체-쌍 최단 경로 문제''' : 그래프 내의 모든 꼭짓점 쌍들 사이의 최단 경로를 찾는 문제이다.

위의 일반화된 문제들은, 전체-쌍 중 단일-쌍만으로 찾아가는 단순 접근 방식보다, 확실히 더 효율적인 알고리즘을 가진다.

== 알고리즘 ==
아래는 이 문제를 해결하기 위한 주요 알고리즘들이다.
* [[데이크스트라 알고리즘]] : 단일-쌍, 단일-출발, 단일-도착 최단 경로 문제를 풀 수 있다.
* [[벨먼-포드 알고리즘]] : 변의 가중치가 음수라면 단일 출발 문제를 풀 수 있다.
* [[A* 탐색 알고리즘]] : 탐색 속도를 높히기 위한 휴리스틱 방법을 사용하며, 단일-쌍 최단 경로 문제를 풀 수 있다.
* [[플로이드-와셜 알고리즘]] : 전체-쌍 최단 경로 문제를 풀 수 있다.

== 응용 ==
최단 경로 알고리즘은 [[웹 지도]] 등에서 실제 위치들 사이에 자동으로 경로를 탐색하여 운전방향을 잡아주고 명확한 경로를 찾는 데에 응용된다.

꼭짓점(V)은 상태, 변(E)은 가능한 전이로 표현되는 그래프와 같이, 만약 비결정적 [[추상 기계]]로 표현되는 어떤 문제에 대하여, 최단 경로 알고리즘은 목표 상태에 도달하기 위한 최적의 선택 순서를 찾거나, 주어진 상태에 도달하는 시간의 하한선을 찾는데 사용될 수 있다.

예를 들어, 한 꼭짓점이 [[루빅스 큐브]]와 같은 퍼즐 상태에 있고 각 방향의 가장자리 끝선이 한 번의 회전과 일치한다면, 최단 경로 알고리즘은 최소로 회전시키는 [[루빅스 큐브]]의 해답을 찾는데 응용할 수 있다.

최단 경로 문제를, [[네트워크]] 또는 [[장거리통신]]에서는 [[최소-지연 경로 문제]]라고 부르기도 하며, [[최광폭 경로 문제]]와 함께 다루어지는 것이 보통이다. 예를 들어, 최단 (최소-지연) 최광폭 경로, 최광폭 최단 (최소-지연) 경로가 있다.

[[6단계 분리]](six degrees of separation) 게임에서, 같은 영화에 출연하는 영화배우들을 나타내는 그래프에서 최단 경로를 찾는 데에 응용되기도 한다.

[[대니 첸]]은 운영 연구, 공장 설비 배치, [[로봇공학]], [[수송]], [[VLSI]] 설계 등에 응용할 수 있음을 언급하였다.

== 관련 문제 ==
{{참고|유클리드 최단 경로|설명=[[컴퓨터 기하학]]에서의 최단경로문제에 대해 알고 싶다면}}

[[이동하는 세일즈맨 문제]]는 모든 경로를 한번씩 지나갔다가 시작점으로 돌아오는 가장 짧은 경로를 찾는 문제이다. 최단 경로 문제와는 달리 이 문제는 [[NP-완전]]하여, 효율적인 해를 찾을 수 없다.([[P-NP 문제]] 참고) 또한, [[최장 경로 문제]] 역시 [[NP-완전]]하다

== 같이 보기 ==
* [[거리측량]]
* [[삼각측량]]
== 각주 ==
{{각주}}
* (Journal of Korea Multimedia Society Vol. 19, No. 8,-A Combination Method of Trajectory Data using Correlated
Direction of Collected GPS Data,
Kwang Min Koo, Heemin Park)https://pdfs.semanticscholar.org/3389/0374991fac0fcc3e12b9a4d9a9f60299b16d.pdf
* (A Big-Data Trajectory Combination Method forNavigations using Collected Trajectory Data,Kwang Min Koo, Taeho Lee, Heemin Park)http://webcache.googleusercontent.com/search?q=cache:EN7Z6lpTSHUJ:www.kpubs.org/article/articleDownload.kpubs%3FdownType%3Dpdf%26articleANo%3DMTMDCW_2016_v19n2_386+&cd=14&hl=ko&ct=clnk&gl=kr
{{전거 통제}}

[[분류:그래프 이론의 계산 문제]]
[[분류:다항 시간 문제]]
[[분류:에츠허르 데이크스트라]]
[[분류:네트워크 이론]]