NAVER 지식백과

마포역에서 강남역까지 가장 빠른 길은 어디일까? 각종 지도에서 제공하는 ‘빠른 길 찾기’ 기능은 최단경로 알고리즘을 통해 빠른 길을 찾아준다.

최단 경로 알고리즘이란 그래프 상의 두 정점 사이를 연결하는 경로 중 가장 짧은 경로를 찾는 절차를 말한다. 여기서 ‘짧다’는 것은 단지 물리적인 거리 뿐 아니라, 시간 거리 혹은 비용 거리 등 다양한 기준이 적용 될 수도 있다. 이렇게 최단 경로를 구하는 알고리즘은 우리가 생활하는 중에 알게 모르게 적용되고 있다. 우리는 경비실에서 택배 온 물건을 찾아오거나 아이스크림을 사러 슈퍼마켓에 다녀오는 등 가까운 곳에 갈 때도 먼 길로 돌아가지 않고 가장 빠른 길로 간다. 또한 새로운 학원을 등록해서 가야하거나 인터넷에서 맛집을 보고 찾아가는 등 어딘가를 처음 가게 될 경우에도 가장 빠른 길을 찾아서 간다.

최단 경로 알고리즘을 이용한 시스템도 흔히 찾아볼 수 있다. 먼저 스마트폰의 지하철 앱을 떠올릴 수 있다. 예를 들어 강남역에서 명동역까지 가려면 어떻게 가야 가장 빨리 갈 수 있을까? 서울에는 지하철 노선이 많기 때문에 가려고 하는 곳이 멀어지면 몇 호선을 타고 어느 역에서 환승해야 가장 빨리 갈지 한눈에 안 보일 때가 많다. 하지만 앱에서 출발지와 목적지만 입력하면 어떻게 가야 가장 빠른지 또는 환승을 가장 적게 하려면 어떻게 가야 하는지 알 수 있다.

또한 자동차 내비게이션도 이와 같은 원리이다. 설날이나 추석 같은 명절이 되면 고향으로 출발하기 전에 자동차에 부착된 내비게이션에 목적지를 입력해서 간다. 자동차의 내비게이션이 여러 고속도로 중 어느 도로가 가장 짧은 지 비교해 가장 적절한 길을 알려주는 것이다. 요즘은 기술이 발달해서 거리뿐만이 아니라 차가 어느 정도 막히는지도 계산해서 알려준다. 이 모두가 최단 경로 알고리즘을 바탕으로 하고 있다.

빠른길찾기 기능을 이용해서 서울 신도림역에서 약수역까지 지하철로 가는 방법을 찾은 결과

이처럼 최단 경로 알고리즘은 우리가 살아가는데 여러 곳에서 사용되고 있다. 이번 글에서는 최단 경로를 찾는 알고리즘 중 가장 대표적인 다익스트라(Dijkstra) 알고리즘에 대해 소개하고자 한다. 간단히 설명하자면, 다익스트라 알고리즘은 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 구하는 방법이다. 이에 대해 자세히 알아보기에 앞서서 바탕이 되는 그래프에 대해 살펴보자.

가중치 그래프의 예. 그림에서 원은 정점을 나타내고 원을 연결하는 선을 간선이라고 한다. 간선에 그려진 숫자는 가중치이다. 최단경로 알고리즘은 이런 가중치 그래프를 바탕으로 한다.

위의 그림에서 원은 정점(定點, 위치가 정해진 점)을 나타내고 원들을 연결하는 선을 간선이라 한다. 말 그대로 정점은 연결의 대상을 나타내고 간선은 두 정점 사이의 연결을 의미한다. 또한 각 선 옆에 숫자가 적혀있는데, 이는 가중치라 한다. 가중치는 간선의 거리나 간선을 이동하는데 걸리는 시간이라 생각하면 된다. 따라서 위와 같은 그래프를 ‘가중치 그래프‘라 한다. 최단 경로 알고리즘은 거리가 긴지 짧은지 알아야 최단 경로를 알 수 있기 때문에 위와 같은 가중치 그래프를 바탕으로 한다.

이제 최단 경로를 찾는 기본 원리에 대해 알아보자. 기본 원리는 너무나 당연하다. 여러 가지의 길이 있을 때 각각의 길을 비교해 거리가 짧은 길을 선택하면 된다. 다음 그림을 보자.

집과 학교 사이의 간단한 지도를 나타낸 것이다. 이전의 그래프에서 정점들을 장소 또는 건물로, 간선을 길로 바꾼 것이다. 위에서 설명한 것처럼 각 길 옆에는 가중치, 즉 거리(물리적 거리, 시간 거리 혹은 비용거리 등 기준은 다양할 수 있다)가 적혀져 있다. 집에서 학교로 가장 빨리 가려면 어떤 길로 가야할까? 먼저 모든 경우의 수를 따져보는 방법이 있겠다. 다음 그림처럼 공원을 거쳐 가는 길, 바로 가는 길, 식당을 거쳐 가는 길, 이렇게 3가지 경우가 있다.

이미지 목록

위의 지도는 단순하여 학교로 가는 모든 경우의 수를 구해서 각각의 거리를 비교해보면 공원을 거쳐 가는 것이 가장 빠르다는 것을 쉽게 알 수 있다. 하지만 우리 생활에서는 위와 같이 쉬운 길만 있지 않다. 길이 복잡한 곳을 가야 할 때도 있다. 위보다 복잡한 길일 때는 어떻게 따지면 될까? 한번 생각해보자.

다영이는 새로 이사해서 전학을 가게 되었다. 다음 날 새로운 학교로 가야하는데 처음 와본 곳이라 가는 길을 모른다. 위에 나와 있는 집 근처의 지도를 통해 가장 빨리 갈 수 있는 길을 알아보려 한다. 어떤 길로 가야 가장 빨리 갈 수 있을까?

이번에는 지도가 꽤 복잡하다. 이전처럼 모든 경우의 수를 세서 비교하는 방법으로는 최단 경로를 구하는 것이 쉽지 않다는 것을 알 수 있다. 다 세더라도 시간이 많이 걸리게 되고 빠짐없이 다 세었는지 빠뜨린 게 있는지 헷갈릴 수 있다. 그렇다면 어떻게 하면 효율적으로 최단 경로를 구할 수 있을까? 다익스트라 알고리즘으로 해결해보자. 먼저 다익스트라 알고리즘의 과정은 다음과 같다.

과정이 머릿속에 와 닿지 않을 수 있다. 직접 과정을 나타낸 그림과 표로 자세히 이해해보자.

먼저 지도상의 건물을 정점으로, 길은 간선으로 바꿔 그래프를 새로 그린다. 그리고 건물들의 최단 거리를 나타내는 표를 만든다. 주의할 점은 표의 칸에 적는 거리는 집에서 각 건물들까지의 최단 거리를 의미한다는 점이다.

이제 각 칸에 거리를 적어보자. 집, 미용실, 슈퍼마켓, 영어 학원에만 거리를 적고 나머지 건물들은 빈 칸으로 나둔다. 빈 칸인 이유는 레스토랑, 은행, 학교는 집과 바로 길로 이어져있지 않으므로 아직 최단 거리를 모르기 때문이다.

※ 집에서 출발하기 때문에 집은 방문한 상태이다. 따라서 색칠해서 방문했다는 표시를 한다.

이제 표를 보니 방문하지 않은 건물들 중 거리가 가장 짧은 곳은 미용실이므로 먼저 미용실로 이동한다. 거리가 적혀있지 않은 칸은 엄청 멀다고 생각하면 된다. 미용실로 이동하니 슈퍼마켓과 은행이 길로 이어져있다. 새로운 길을 찾았으니 새로운 길이 짧은지 전에 알아본 길이 짧은지 비교해 봐야 한다.

① 은행까지의 거리는 집에서부터 미용실까지 거리(5)와 미용실부터 은행까지의 거리(11)의 합인 16이 된다.
② 슈퍼마켓까지의 거리는 위와 같은 방법으로 8이 된다. 하지만 표를 보니 슈퍼마켓은 전 과정에서 미리 구했었다. 따라서 둘을 비교하면 미용실을 거쳐 가는 길이 더 빠르므로 표의 슈퍼마켓의 칸에는 거리가 10에서 8로 새롭게 바뀐다. 이러한 방식으로 최단 경로를 구하지 않고 거쳐 가는 것보다 바로 가는 것이 더 짧을 것이라고 단정 지으면 안 된다는 사실을 알 수 있다. 실제로는 어디론가 이동할 때 거리만 고려하지 않는다. 가는 길이 짧더라도 신호등이 많거나 차가 막히면 가는데 더 오래 걸리기 때문이다.

※ 이제 미용실도 방문했으므로 노란색으로 칠한다. 미용실로 온 경로도 색칠한다.

이번에도 같은 규칙으로 가보지 않은 건물 중 거리가 가장 짧은 슈퍼마켓을 방문한다. 슈퍼마켓으로 가보니 레스토랑, 은행, 영어 학원으로의 길이 보이게 된다. 이번에도 새로운 길을 전과 비교해보자.

① 레스토랑까지의 거리는 5+3+3으로 11이다.
② 은행까지는 5+3+10으로 18이지만 이전 과정에서 구한 거리와 비교해보면 이전 과정이 더 짧으므로 은행 칸에 있는 거리는 그대로 유지된다.
③ 영어학원도 마찬가지로 이전 과정이 더 짧으므로 바뀌지 않는다.

※ 슈퍼마켓도 칠한다. 슈퍼마켓은 미용실을 거쳐 왔으니 길에 표시한다.

같은 규칙으로 가보지 않은 건물 중 거리가 가장 짧은 영어학원을 방문한다. 이번에도 새로운 길을 전과 비교해보자.

① 은행까지는 9+7로 16이지만 이전 과정에서 구한 거리와 비교해보면 이전 과정과 같으므로 은행 칸에 있는 거리는 그대로 유지된다.
② 학교까지의 거리가 9+12=21로 추가된다.

※ 영어학원도 칠하고 온 길도 칠한다.

같은 규칙으로 가보지 않은 건물 중 거리가 가장 짧은 레스토랑을 방문한다. 이번에도 새로운 길을 전과 비교해보자.

① 은행까지는 11+4로 15이다. 이전 과정에서 구한 거리와 비교해보면 더 짧으므로 은행까지의 거리는 15가 된다.

※ 레스토랑도 칠한다. 레스토랑에 온 길도 칠한다.

같은 규칙으로 가보지 않은 건물 중 거리가 가장 짧은 은행을 방문한다. 이번에도 새로운 길을 전과 비교해보자.

① 학교까지는 은행까지의 거리(15)과 은행과 학교까지의 거리(2)를 더해 17이 된다. 이전 과정에서 구한 거리(21)과 비교하면 더 짧으므로 학교까지의 거리가 17이 된다.

※ 은행과 은행에 온 길을 칠한다.

이제 가보지 않은 건물 중 거리가 가장 짧은 곳이 목적지인 학교가 되었다. 이로서 학교까지의 최단 거리를 17인 것을 알게 된 것이다.

※ 학교를 칠하고 학교로 온 길을 칠한다

이 과정을 거쳐 다영이는 어느 길로 가야 가장 집에서 학교로 빨리 갈 수 있는지 알 수 있다. 위보다 더 복잡한 길로 이루어진 지도이더라도 위와 같은 방법으로 표를 작성해 칸을 하나씩 차근차근 채워나가면 최단 경로를 쉽게 구할 수 있다. 각자 공책에 아무 형태의 그래프를 그리고 혼자서 같은 과정으로 연습해보길 바란다.

최단 경로를 찾는 알고리즘에는 지금까지 소개한 다익스트라 알고리즘 외에도 플로이드 알고리즘, 벨만 포드 알고리즘이 있다. 플로이드 알고리즘은 모든 정점간의 최단 경로를 구할 수 있고, 벨만 포드 알고리즘은 가중치가 음수이더라도 최단 경로를 구할 수 있다는 장점이 있지만, 둘 다 다익스트라 알고리즘에 비해 시간이 오래 걸린다는 단점이 있다.

도시 계획이나 집적회로의 설계에도 최단경로 알고리즘이 적용된다.

앞서서 말한 것처럼 최단 경로 알고리즘은 네이버, 구글 등 여러 검색 엔진의 지도 서비스, CRS(자동차 내비게이션 시스템), 지하철 혹은 버스 노선 앱에서 활용된다. 또한 건물의 위치를 효율적으로 정하기 위해 이용하기도 한다. 뿐만 아니라 군사 공학, 건축 공학, 통신망 설계, VLSI(초고밀도 집적 회로) 설계 등 여러 분야에서 다양하게 이용되고 있다.