[[분류:기하학]][[분류:이산수학]]

[목차]
== 개요 ==
최단거리([[最]][[短]][[距]][[離]])는 두 점 사이의 [[길이|거리]] 중 가장 짧은 크기를 갖는 것을 말한다. 크게 이산수학적 최단거리와 기하학적 최단거리로 나뉜다. 일반적으로 최단거리라 함은 후자를 뜻한다.

== [[이산수학]]에서 ==
[include(틀:이산수학)]

[[경우의 수]] 문제중 유형화된 문제중 하나이다. 일반적으로 여러개의 점들 중에서 어떤점부터 다른 한 점까지의 최단 경로를 묻는 문제로 나온다. 아래의 기하학적 최단거리와 구별하기 위해 '점을 거쳐야 하는 규칙'을 추가한다.

=== 풀이 ===
이 문제를 푸는 방법은 3가지로 나눌 수 있다.
==== 1,1,1법칙([[시행착오#s-3|시행착오법]]) ====
가장 귀찮지만 가장 생각은 안 하고 문제를 풀 수 있는 방법이다. 또한 후술할 법칙과는 달리 문제가 바뀌어도 풀이법에 크게 변화가 없는, 범용성이 뛰어나다.
1,1,1 법칙은 다음과 같다.
||(0,1)||(1,1)||(도착)||
||(출발)||(1,0)||(2,0)||
이렇게 생긴 지도에서 최단거리의 개수는 다음과 같다.
||(0,1)-''(1)''||(1,1)-''(2)''||(도착)-''(3)''||
||(출발)-''(1)''||(1,0)-''(1)''||(2,0)-''(1)''||
이렇게, 출발이 있는 행과 열의 포인트들에 1이라고 쓰고 어느 한 점의 최단거리의 개수를 그 점으로 갈 수 있는 점들의 최단거리의 개수의 합으로 하는 것 이다.

실수할 확률이 높기 때문에 이 방법이 후술할 방법보다 유용하지 않을 수도 있다. 하지만 대부분의 연습문제의 경우 지도가 복잡하거나, 혹은 장애물이 많아 후술할 방법을 쓰면 생각할 것이 매우 복잡해지기 때문에 이 방법이 유용하게 쓰인다.
==== [[순열#s-3|동자순열]](같은 것을 포함한 순열[* 고등학교 확률과 통계(확통)에서는 이 용어로 학습한다.])을 이용한 풀이 ====
||(0,2)||(1,2)||(2,2)||(도착)||
||(0,1)||(1,1)||(2,1)||(3,1)||
||(출발)||(1,0)||(2,0)||(3,0)||
위처럼 생긴 지도에서 최단거리의 길이는 5이다. 또한 모든 최단거리는 오른쪽 3칸, 위쪽 2칸으로 구성되어 있음을 알 수 있다. 다시말해, 오른쪽 3번, 위쪽 2번을 배열해서 만든 배열은 모두 최단거리라는 것 이다. 따라서 동자순열의 원리에 따라 위 예시의 최단경로의 개수는 [math(\frac{5!}{3!2!})]과 같다.

이 풀이를 이용한 해법은 일반적으로 다음과 같이 정리할 수 있다.
> [math(N{\sf x}M)]크기의 지도에서 최단경로의 개수는 [math(\frac{(N+M)!}{N!M!})]와 같다.
==== [[조합]]을 이용한 풀이 ====
조합을 이용한 풀이는 동자순열을 이용한 풀이와 맥락이 비슷하다. 다만 그 경우의 수를 구하는 방법이 조금 다를 뿐이다.
조합을 이용해 최단경로의 개수를 구하는 방법은 일반적으로 다음과 같다.
> [math(N{\sf x}M)]크기의 지도에서 최단경로의 개수는 [math(N+M \choose M)]와 같다. ([math(p \choose q)]은 [[조합]]이다.)

=== 크기 ===
격자 형태로 이루어진 이동 경로라는 점에서, 그 크기를 '''[[노름(수학)#s-4.2.2|택시 노름]]'''(Taxicab norm)[* 맨해튼 노름(Manhattan norm)이라고도 한다.]으로 정의할 수 있으며 모든 이동경로의 길이의 [[절댓값]]을 더한 값이 된다. 이는 [[택시 기하학|택시 거리 공간]]에서 아래의 기하학적 최단거리와 [[연결고리]]를 이룬다.

== [[기하학]]에서 ==
[include(틀:기하학·위상수학)]
=== [[유클리드 기하학]] ===
두 점을 잇는 선분을 죽 그어주면 되는 간단한 방법으로 구할 수 있다. 도형 내에서는 [[대각선]]이라고도 한다.

해당 선분의 크기는 따로 '''[[유클리드 노름]]'''(Euclidean norm)이라고 한다.
=== [[비유클리드 기하학]][anchor(측지선)] ===
여기서는 '''측지선'''(geodesic, [[測]][[地]][[線]])이라는 이름으로 부른다.[* 정확히는 곡면 위에서 최단거리 곡선은 측지선이지만, 그 역이 항상 성립하는 것은 아니다. 수학적 정의에 따르면 벡터 위의 점을 [[미분|[math(\cdot=\displaystyle \frac{\operatorname{d}}{\operatorname{dt}})]라는 연산자라고 뒀을 때]], 다차원공간에 놓여진 2차원 재매개화가 가능한 곡선 [math(\gamma)]에 대하여  점 [math(\gamma(t))]에서 [math(\ddot \gamma(t))]가 0 혹은 해당 곡면에 직교하는 곡선을 의미한다.][* 또한 앞의 정의에 따라서, 모든 측지선은 상수인 속력을 갖게 된다. [math(\ddot \gamma\cdot\dot\gamma=0)]이므로 [math(\displaystyle \frac{\operatorname{d}}{\operatorname{dt}}\lVert \dot \gamma \rVert^{2}=2\ddot \gamma\cdot\dot\gamma=0)]이 되기 때문.] 위의 대각선과는 달리, 이 측지선은 [[미분 기하학]]을 이용해서 구해야 하기 때문에 상당한 [[노가다(수학)|노가다]]가 된다.

측지선의 대표적인 예로, [[비유클리드 기하학#s-3.1|구면기하학]]에서의 대원(Great circle)이 있는데, 해당 [[구(도형)|구]]의 지름에 대한 원 둘레 길이이다.

상술했듯 [[택시 기하학]]에서는 [[노름(수학)#s-4.2.2|택시 노름]]이라는 이름으로 불린다.