차량을 운전해 낯선 곳을 찾아가야 할 때 내비게이션 장치는 필수적이다. 내비게이션 장치의 가장 기본적인 기능은 출발점과 도착점 사이의 최단 경로(Shortest Path)를 찾아 사용자에게 안내하는 것이다. 최단 경로 찾기는 지도의 어느 한 출발점에서 도착점까지의 최단 경로를 찾는 것인데, 이를 해결하는 기본적인 알고리즘으로 다익스트라(Dijkstra, 1930-2002)의 ‘최단 경로 알고리즘’을 들 수 있다. 다익스트라는 1972년 컴퓨터 분야 최고의 튜링상을 수상한 네델란드의 컴퓨터 과학자이다. 다익스트라 알고리즘은 내비게이션 장치, 맵퀘스트(Mapquest)나 구글 맵스(Google Maps)와 같은 웹 서비스에 사용되며 네트워크 분야, 소셜 네트워크 분석, 산업공학과 경영공학, 로봇공학, 교통공학, VLSI 디자인 등 수많은 분야에 응용되고 있다.

 

▲ [그림 1]~[그림 5] 다익스트라 알고리즘을 바탕으로 최단 경로를 찾는 과정


다익스트라 알고리즘은 지도상의 점들을 2개의 그룹 (A, B)으로 분류한다. 그룹 A에는 출발점으로부터 최단 경로가 확정된 점들이 속하고, 그룹 B에는 출발점으로부터 최단 거리가 확정되지 않은 점들이 속한다. 여기서 ‘확정되었다’는 것은 그룹 A에 속한 각 점과 출발점 사이의 최단 경로 및 최단 거리가 결정됐으며 더 이상 바뀌지 않는다는 것을 의미한다.

알고리즘은 처음에 출발점을 그룹 A에 포함시킨다. 왜냐하면 출발점에서 출발점 자신까지의 최단 경로의 거리는 0이기 때문이다. 출발점이 아닌 모든 다른 점들은 그룹 B에 넣는다([그림 2]). 그리고 출발점과 직접 연결된 각 점의 거리를 계산한다 ([그림 3]).

그 다음은 그룹 B의 점들 중에서 출발점으로부터 가장 가까운 점의 최단 경로 및 최단 거리를 확정한다. 예를 들어, [그림 4]에서 b는 출발점으로부터 거리가 5이고 c는 출발점으로부터 거리가 15이므로 b의 최단 경로가 확정되고, b를 그룹 A에 넣는다. 그리고 방금 최단 거리가 확정된 점 b와 직접 연결된 B그룹의 점들의 거리를 각각 갱신한다. 이 때 말하는 갱신이란 각 점의 현재 거리와 방금 최단 거리가 확정된 점을 거쳐서 가는 거리를 비교하여 최소값을 취하는 과정을 의미한다. [그림 5]는 c와 d의 거리가 방금 최단 거리가 확정된 점 b를 거쳐서 c와 d로 가는 경로 (a→b→c 와 a→b→d)의 거리로 각각 갱신된 것을 보여 준다.

다익스트라 알고리즘은 이러한 확정과 갱신을 반복하여 다음과 같이 출발점 a로부터 도착점 d까지의 최단 경로를 찾는다. 이 때 도착점까지의 최단 거리는 15이다.

다익스트라 알고리즘은 출발점에서 도착점까지의 최단 경로를 찾을 때까지 수행되는데, 출발점으로부터 거리가 가까우면서 동시에 도착점의 방향과 무관한 점들의 최단 경로를 먼저 찾는 헛수고를 하는 경우가 있다. [그림 6]에서 출발점이 a이고 도착점이 d일 때, 다익스트라 알고리즘은 도착점과 무관한 방향에 있는 점 e, f, g, h, i 모두의 최단 경로를 찾은 후에서야 도착점 d를 향해 최단 경로 찾기를 수행한다.

이러한 단점을 보완하는 대표적인 알고리즘이 바로 A*(A star) 알고리즘이다. A* 알고리즘은 출발점을 제외한 각각의 점에 대해 도착점까지의 예상 거리 (예를 들어, 지도상의 좌표로 계산된 직선 거리)를 추가하여 고려한다. 즉, A* 알고리즘은 각 지점마다 출발점으로부터의 거리뿐만 아니라 도착점까지의 예상 거리의 합까지 고려하여 다익스트라 알고리즘을 수행한다. 따라서 도착점과 반대 방향에 있는 점([그림 6]의 e, f, g, h, i)이 출발점에 가깝다 하더라도, A* 알고리즘은 도착점 방향에 있는 점들의 최단 경로를 우선적으로 계산해 출발점과 도착점간의 최단 경로를 다익스트라 알고리즘보다 빨리 찾는다. A* 알고리즘 외에도 도로 망이 시간에 따라 그리 많이 변하지 않는다는 것을 감안하여, 신속히 최단 경로를 찾기 위해서 (출발점과 도착점이 주어지기 전에) 미리 도로 망에 대해 선처리(preprocessing)를 하는 실질적인 알고리즘들도 많이 개발되어 있다. 예를 들어, SHARC [1], Contraction Hierarchies [2], ALT(A* search, Landmarks, Triangle inequality) [3], Reach Based Pruning [4], arc-Flags [5], Highway Node Routing [6] 등이 있다.

저작권자 © 연세춘추 무단전재 및 재배포 금지