[[분류:나무위키 수학 프로젝트]][[분류:기하학]][[분류:이산수학]] [목차] == 개요 == 두 점 사이의 [[길이|거리]] 중 가장 짧은 크기를 갖는 것. 크게 이산수학적 최단거리와 기하학적 최단거리로 나뉜다. 일반적으로 최단거리라 함은 후자를 뜻한다. == [[이산수학]]에서 == [include(틀:이산수학·수리논리학)] [[경우의 수]] 문제중 유형화된 문제중 하나이다. 일반적으로 여러개의 점들 중에서 어떤점부터 다른 한 점까지의 최단 경로를 묻는 문제로 나온다. 아래의 기하학적 최단거리와 구별하기 위해 '점을 거쳐야 하는 규칙'을 추가한다. === 풀이 === 이 문제를 푸는 방법은 3가지로 나눌 수 있다. ==== 1,1,1법칙([[노가다(수학)|노가다]]) ==== 가장 귀찮지만 가장 생각은 안 하고 문제를 풀 수 있는 방법이다. 또한 후술할 법칙과는 달리 문제가 바뀌어도 풀이법에 크게 변화가 없는, 범용성이 뛰어나다. 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)이라는 이름으로 부른다. 위의 대각선과는 달리, 이 측지선은 [[미분 기하학]]을 이용해서 구해야 하기 때문에 상당한 [[노가다(수학)|노가다]]가 된다. 측지선의 대표적인 예로, [[비유클리드 기하학#s-3.1|구면기하학]]에서의 대원(Great circle)이 있는데, 해당 [[구(도형)|구]]의 지름에 대한 원 둘레 길이이다.