최단 경로 알고리즘, 네비게이션 작동 원리 알고보니…'대박'

[헤럴드 리뷰스타=김희은 기자] 최단 경로 알고리즘이 화제다. 최단 경로 알고리즘이란 그래프 상의 두 정점 사이를 연결하는 경로 중 가장 짧은 경로를 찾는 절차를 일컫는다. 여기서 ‘짧다’는 것은 단지 물리적인 거리 뿐 아니라, 시간 거리 혹은 비용 거리 등 다양한 기준이 적용 될 수도 있다. 이렇게 최단 경로를 구하는 알고리즘은 우리가 생활 속에 녹아있다.일상에서 자주 사용하는 ‘빠른 길 찾기’는 최단 경로 알고리즘을 활용한다. 이는 스마트폰의 지하철 앱이 해당하며 앱에서 출발지와 목적지만 입력하면 어떻게 가야 가장 빠른지 또는 환승을 가장 적게 하려면 어떻게 가야 하는지 알려준다. 자동차 네비게이션 또한 이와 같은 원리이다. 출발하기 전에 자동차에 부착된 네비게이션에 구체적인 목적지의 위치를 입력을 하면, 여러 고속도로 중 어느 도로가 가장 짧은 지 비교해 가장 적절한 길을 선정해준다. 소식을 접한 네티즌들은 “최단 경로 알고리즘, 일상 생활에서 자주 사용하는거네”,“최단 경로 알고리즘, 진짜 편리하다 신기해”,“최단 경로 알고리즘, 뭔가 했더니 네비게이션이구나” 등의 뜨거운 반응을 보이고 있다. idsoft3@reviewstar.net