네이버·구글도 사용하는 최단 경로 알고리즘은 무엇?

최단 경로 알고리즘.

최단 경로 알고리즘에 대해 누리꾼들의 관심이 점차 높아지고 있다.

최단 경로 알고리즘이란 그래프 상의 두 정점 사이를 연결하는 경로 가운데 가장 짧은 경로를 찾는 절차를 말한다.

여기서 ‘짧다’는 표현은 단지 물리적 거리 뿐 아니라 시간 거리, 비용 거리 등 다양한 기준이 적용된다.

한편 최단 경로를 구하는 알고리즘이 우리 일상 생활에도 많이 통용되고 있는 것으로 전해졌다.

스마트폰의 지하철 앱의 경우 출발지와 목적지만 입력하면 어떻게 가야 가장 빠른지 또는 환승을 가장 적게 하려면 어떻게 가야 하는지 알려준다.

자동차 네비게이션 역시 고소고로 주행중 어느 도로가 가장 짧은지 비교해 가장 적절한 길을 알려주며 거리 뿐 아니라 어느 정도 막히는지도 계산해서 알려준다.


김민수 기자 hms@