내비게이션이 가장 빠른 길을 찾는 방법, 최단 경로 알고리즘

내비게이션은 도로망을 교차로라는 점과 도로라는 선으로 이루어진 그래프로 바꾸고, 각 선에 걸리는 시간을 숫자로 붙인 뒤, 출발점에서 도착점까지 숫자의 합이 가장 작은 경로를 계산한다. 이 계산의 뼈대는 1956년 네덜란드의 에츠허르 다익스트라가 고안한 알고리즘이다. 다익스트라 알고리즘은 출발점에서 가까운 곳부터 차례로 확정해 나가는 방식으로, 선마다 붙은 숫자가 음수만 아니면 언제나 정확한 최단 경로를 찾는다.

모든 길을 다 따져 보면 안 되는 이유

가장 쉬운 방법은 가능한 모든 경로를 늘어놓고 비교하는 것이다. 그러나 교차로가 조금만 많아져도 경로의 수는 폭발적으로 늘어난다. 바둑판처럼 생긴 도로에서 가로 20칸, 세로 20칸을 돌아가지 않고 가는 경로만 해도 1천억 가지가 넘는다. 실제 도로망에는 교차로가 수백만 개 있으므로, 모든 경로를 따지는 방법으로는 답이 나오기 전에 목적지에 도착하고 만다.

가까운 곳부터 확정하기

다익스트라 알고리즘은 다르게 접근한다. 처음에는 출발점까지의 거리만 0으로 알고, 다른 모든 교차로까지의 거리는 아직 모른다고 적어 둔다. 그다음 아직 확정하지 않은 교차로 가운데 지금까지 알려진 거리가 가장 짧은 곳을 하나 골라 확정한다. 그 교차로에서 바로 이어진 이웃들을 살펴, 그곳을 거쳐 가는 편이 더 빠르면 이웃까지의 거리를 고쳐 적는다. 이 일을 도착점이 확정될 때까지 되풀이한다.

가장 가까운 곳을 확정해도 되는 이유는 간단하다. 그곳보다 먼 교차로를 거쳐 돌아오면 거리가 더 늘어날 수밖에 없기 때문이다. 이 논리는 도로마다 걸리는 시간이 0 이상이라는 조건에서만 성립한다. 지나가면 시간이 줄어드는 길은 현실에 없으니 길 찾기에서는 문제가 되지 않는다. 결과적으로 탐색은 출발점에서 물결이 퍼지듯 넓어지며, 각 교차로는 한 번씩만 확정된다.

목적지 쪽을 먼저 본다

다익스트라 알고리즘은 정확하지만 목적지와 반대 방향도 똑같이 넓혀 간다. 서울에서 부산으로 가는 길을 찾으면서 인천 쪽 골목까지 살펴보는 셈이다. 1968년에 나온 A* 알고리즘은 여기에 추정치를 더한다. 각 교차로에서 목적지까지의 직선거리처럼, 실제 남은 거리보다 결코 길지 않은 어림값을 함께 고려해 목적지 쪽으로 향한 교차로를 먼저 살핀다. 어림값이 실제보다 길게 잡히지만 않으면 A*도 최단 경로를 정확히 찾으면서, 살펴보는 교차로 수는 크게 줄어든다.

방법	살펴보는 범위	특징
모든 경로 비교	가능한 경로 전부	작은 지도에서만 가능
다익스트라	출발점 둘레를 고르게	정확하지만 넓게 탐색
A*	목적지 쪽으로 치우쳐	어림값이 좋을수록 빠름

큰 지도에서는 미리 계산해 둔다

나라 전체의 도로망에서 몇 초 안에 답을 내려면 이것으로도 부족하다. 실제 길 찾기 서비스는 질문이 오기 전에 지도를 미리 가공해 둔다. 대표적인 생각은 도로에 위계를 매기는 것이다. 먼 거리를 가는 최단 경로는 대개 출발 직후 큰길로 나가 고속도로를 타고, 도착 직전에야 골목으로 들어간다. 그래서 중요한 도로끼리의 지름길을 미리 계산해 두면, 실제 탐색은 출발지와 목적지 근처의 골목과 미리 만든 지름길만 살피면 된다. 이런 방식으로 탐색해야 할 교차로를 수백만 개에서 수백 개 수준으로 줄일 수 있다.

같은 문제는 도로 밖에서도 쓰인다. 인터넷에서 데이터가 오가는 길, 전력이 흐르는 송전망, 택배가 여러 물류 센터를 거쳐 가는 경로도 모두 점과 선의 그래프로 나타낼 수 있다. 이때 선에 붙는 숫자는 시간이 아니라 지연, 비용, 손실이 되지만 계산 방법은 같다. 다익스트라 알고리즘이 반세기가 넘도록 쓰이는 것은 이렇게 쓰임새가 넓기 때문이다.

남은 과제, 바뀌는 시간

어려움은 도로마다 걸리는 시간이 고정되어 있지 않다는 데 있다. 출근 시간의 교통량, 사고, 공사, 신호 대기 때문에 같은 길도 시각에 따라 걸리는 시간이 달라진다. 지금 출발하는 차가 30분 뒤 지날 도로의 상황까지 예측해야 하므로, 길 찾기는 계산 문제이면서 동시에 예측 문제가 된다. 또 모든 차가 같은 최단 경로를 안내받으면 그 길이 막혀 더 이상 최단 경로가 아니게 되는 문제도 있다. 개별 운전자에게 가장 빠른 길과 도로망 전체가 덜 막히는 길이 서로 다를 수 있다는 점은 교통 공학이 아직 풀고 있는 숙제다.