최단 경로 알고리즘, 길찾기부터 건물 위치까지..."어디까지 사용?"

최단 경로 알고리즘 / 네이버 화면 캡쳐

최단 경로 알고리즘, 길찾기부터 건물 위치까지..."어디까지 사용?"

최단 경로 알고리즘이 어떤 뜻인지에 대한 관심이 뜨겁다.

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

최단 경로 알고리즘의 ‘짧다’는 것은 단지 물리적인 거리 뿐 아니라, 시간 거리 혹은 비용 거리 등 다양한 기준이 적용 될 수도 있다. 특히 최단 경로 알고리즘은 우리 생활 속에서도 많이 적용되고 있다.

최단 경로의 알고리즘은 여러 포털 사이트의‘빠른길찾기’에서 활용된다. 최단 경로 알고리즘을 이용한 시스템은 다양한 지도 서비스에서 흔히 찾아볼 수 있다.

또한 최단 경로 알고리즘은 스마트폰의 지하철 어플리케이션에서도 사용된다. 앱에서 출발지와 목적지만 입력하면 어떻게 가야 가장 빠른지 또는 환승을 가장 적게 하려면 어떻게 가야 하는지 알려준다.

그리고 자동차 네비게이션도 이와 같은 원리이다. 자동차에 부착된 네비게이션에 목적지를 입력해 안내된 길을 따라간다. 자동차의 네비게이션이 여러 고속도로 중 어느 도로가 가장 짧은 지 비교해 가장 적절한 길을 알려주는 원리이다.

요즘은 기술이 발달해서 거리뿐만이 아니라 차가 어느 정도 막히는지도 계산해서 알려준다. 이 모두가 최단 경로 알고리즘을 바탕으로 하고 있다.

또한 건물의 위치를 효율적으로 정하기 위해 이용되기도 한다고 전해진다.

한편, ‘최단 경로 알고리즘’ 기사를 접한 네티즌들은 “‘최단 경로 알고리즘’ 많이 사용된다" “‘최단 경로 알고리즘’ 잘 활용해야겠다” “‘최단 경로 알고리즘’ 신기하네” 등의 반응을 보였다.

인터넷팀 박현주 기자[e-mail]