최단 경로(Shortest path)

지도 앱이 길을 찾을 때, 도로망은 교차로(꼭짓점⁠, vertex⁠)와 도로(변)로 된 그래프이고 각 도로를 지나는 데 걸리는 시간이 변의 가중치입니다. 찾는 것은 가중치의 합이 가장 작은 길입니다. 가능한 길의 수는 교차로 수에 따라 기하급수적으로 늘어나서 하나하나 비교할 수는 없습니다.

실마리는 최단 경로의 일부도 최단 경로라는 사실입니다. v까지 가장 짧은 길이 u를 거쳐 온다면, 출발점에서 u까지도 가장 짧게 왔어야 합니다. 그래서 출발점 s가 아닌 점 v까지의 거리 $d(v)$는 이웃 u들의 $d(u) + w(u, v)$ 가운데 가장 작은 값입니다(위의 식). 큰 최적화⁠(optimization)⁠ 문제를 한 번에 풀지 않고, 작은 조각의 최적을 이어 붙이는 셈입니다.

1959년 네덜란드의 컴퓨터 과학자 에츠허르 데이크스트라가 발표한 다익스트라 알고리즘은 이 식을 가까운 곳부터 채웁니다. 점마다 잠정 거리, 곧 지금까지 찾은 길 가운데 가장 짧은 것의 길이를 적어 둡니다(아직 길을 못 찾았으면 ∞). 이 값은 더 좋은 길이 나타나면 줄어들 수 있습니다. 매 단계 아직 확정하지 않은 점 가운데 잠정 거리가 가장 작은 점을 골라 그 값을 진짜 거리로 확정하고, 그 점을 거쳐 가면 더 가까워지는 이웃이 있으면 그 이웃의 잠정 거리를 줄입니다. 가중치가 음수가 아니면 지금 가장 작은 잠정 거리는 다른 길로 돌아가도 더 줄어들 수 없으니, 확정해도 안전합니다. 확정된 점들의 집합⁠(set)⁠이 출발점에서 물결처럼 퍼져 나갑니다. 지금 가장 좋아 보이는 점을 골라 되돌아보지 않으니, 욕심쟁이 알고리즘⁠(greedy algorithm)⁠이 정확한 답을 주는 대표적인 경우입니다. 잠정 거리가 가장 작은 점을 빠르게 꺼내려고, 가장 작은 값을 늘 맨 앞에 두는 자료 구조인 우선순위 큐(흔히 힙⁠(heap)⁠으로 만듭니다)에 점들을 담아 둡니다. 점마다 어느 이웃에서 왔는지 기록해 두면, 그 화살표들이 출발점을 뿌리로 하는 트리(최단 경로 트리⁠(tree)⁠)를 이룹니다.

왼쪽 위 출발점에서 시작합니다. 아래 ◀ ▶로 한 단계씩 진행해 보세요. 청록 점은 확정, 노란 점은 잠정 거리만 아는 점, 회색 점은 아직 못 본 점(∞)입니다. 점을 누르면 목표(분홍 고리)가 바뀝니다.

변의 가중치: . 가중치를 모두 1로 바꿔 보세요. 가중치가 모두 1이면 다익스트라 알고리즘은 출발점에서 한 걸음, 두 걸음 떨어진 점들을 층층이 훑는 너비 우선 탐색⁠(breadth-first search)⁠이 되고, 거리는 걸음 수가 됩니다. 새 도로망

음수 가중치가 있으면 나중에 음수 변을 지나 더 짧아질 수 있어서 확정이 더는 안전하지 않습니다. 이런 일은 일방통행처럼 변에 방향이 있는 그래프에서 의미가 있습니다. 방향 없는 변의 가중치가 음수이면 그 변을 오가기만 해도 끝없이 짧아지니까요. 일반적으로 한 바퀴 돌면 길이의 합이 음수가 되는 고리가 있으면 최단 경로 자체가 없습니다. 그런 고리가 없을 때는 벨먼–포드 방법(1950년대에 미국의 수학자 리처드 벨먼과 레스터 포드가 따로 내놓았습니다)을 씁니다. 모든 변에 대해 '이 변을 거쳐 가면 더 짧아지는가'를 확인해 잠정 거리를 줄이는 일을 (점의 개수 − 1)번 되풀이하는 방법입니다. 한 번 더 되풀이해서도 줄어드는 곳이 있으면 음수 고리가 있다는 뜻입니다. 지도 앱은 A* 탐색⁠(A* search)⁠을 흔히 씁니다. 다익스트라처럼 잠정 거리만 보지 않고, 거기에 그 점에서 목표까지의 직선거리를 더한 값이 가장 작은 점부터 확정해서 목표 쪽을 먼저 살핍니다. 변의 가중치가 실제 거리라면 피타고라스 정리⁠(Pythagorean theorem)⁠로 잰 직선거리는 남은 실제 길보다 결코 길지 않습니다. 이렇게 남은 거리를 부풀리지 않는 어림을 쓰면 답은 여전히 최단입니다(가중치가 시간이라면 직선거리를 가장 빠른 속력으로 나눈 값을 씁니다). 모든 두 점 사이의 최단 거리를 한꺼번에 구하는 방법도 있습니다. 행렬의 곱⁠(matrix multiplication)⁠에서 곱셈을 덧셈으로, 합을 최솟값으로 바꾼 '최소-합 곱⁠(min-plus product)⁠'을 생각하면, 그 (i, j) 성분은 i에서 어떤 점 k를 거쳐 j로 가는 길이 가운데 가장 작은 값이 됩니다. 대각선을 0으로 둔 변 길이 표에 이 곱을 거듭하면 변을 두 개 이하, 세 개 이하, … 쓰는 길까지 차례로 고려하게 됩니다. 음수 고리가 없으면 (점의 개수 − 1)개까지만 보면 되므로, 결국 모든 쌍의 최단 거리가 나옵니다. 가중치가 음수가 아니면, 이렇게 얻은 거리표에 이 곱을 한 번 더 해도 바뀌지 않는다는 것이 곧 삼각부등식⁠(triangle inequality)⁠ $d(i, k) \le d(i, j) + d(j, k)$입니다. 삼각부등식을 화살표의 합성으로, $d(i, i) = 0$을 항등 화살표⁠(identity arrow)⁠로 읽는 풍부화된 범주⁠(enriched category)⁠의 눈으로 보면, 최단 거리표는 도로망이 자유롭게 생성하는 '거리의 범주⁠(category)⁠'입니다.

이어지는 곳. 그래프 대신 매끄러운 곡면 위에서 두 점을 잇는 가장 짧은 곡선(예를 들어 지구 위의 대원 항로⁠(great-circle route)⁠)이 측지선⁠(geodesic)⁠입니다. 좁은 세상⁠(small world)⁠은 거대한 연결망에서 최단 경로가 놀랄 만큼 짧다는 관찰이고, 모든 도로를 적어도 한 번씩 돌아야 하는 우편배달부 문제⁠(Chinese postman problem)⁠에서는 최단 경로가 오일러 경로⁠(Euler path)⁠를 만드는 부품으로 쓰입니다. 아무 길이나 골라 떠도는 무작위 행보⁠(random walk)⁠로 목표에 닿으려면 보통 최단 거리보다 훨씬 많은 걸음이 듭니다. 모든 점을 이어 주는 가장 짧은 도로망을 찾는 것은 다른 문제로, 한 점에서의 거리 대신 변 길이의 합을 줄이는 최소 신장 트리⁠(minimum spanning tree)⁠가 답입니다. 도로망이 한꺼번에 차를 얼마나 많이 보낼 수 있는지는 최대 흐름 최소 절단 정리⁠(max-flow min-cut theorem)⁠가 답합니다.

한 낱말을 다른 낱말로 바꾸는 데 필요한 최소 편집 횟수(글자 하나를 넣기, 지우기, 바꾸기를 각각 한 번으로 셉니다)를 편집 거리⁠(edit distance)⁠라고 합니다. 예를 들어 kitten을 sitting으로 바꾸려면 k→s, e→i로 두 번 바꾸고 g를 한 번 넣어 모두 세 번이 듭니다. 이것도 최단 경로입니다. 두 낱말의 앞부분끼리 짝지은 표의 칸을 점으로 봅니다. 넣기와 지우기는 가로나 세로로 한 칸, 바꾸기는 대각선으로 한 칸 가는 가중치 1인 변이고, 같은 글자를 그대로 두는 대각선 이동은 가중치 0인 변입니다. 그러면 표의 왼쪽 위에서 오른쪽 아래까지 가는 최단 경로의 길이가 편집 거리입니다.