최단 경로 알고리즘, 지하철앱, 네비게이션 등 알게 모르게 실생활에서 사용돼

↑ 사진=MBN

최단 경로 알고리즘이란 그래프 상의 두 정점 사이를 연결하는 경로 중 가장 짧은 경로를 찾는 절차를 말합니다. 여기서 '짧다'는 것은 단지 물리적인 거리 뿐 아니라, 시간 거리 혹은 비용 거리 등 다양한 기준이 적용 될 수 있습니다.

이렇게 최단 경로를 구하는 알고리즘은 우리가 생활하는 중에 알게 모르게 적용되고 있습니다.

우선, 스마트폰의 지하철 앱을 떠올릴 수 있습니다. 예를 들어 강남역에서 명동역까지 가장 빠른길을 찾기 위해 노선표를 살펴보지만 서울에는 지하철 노선이 많기 때문에 가려고 하는 곳이 멀어지면 몇 호선을 타고 어느 역에서 환승해야 가장 빨리 갈지 한눈에 안 보일 때가 많습니다. 하지만 앱에서 출발지와 목적지만 입력하면 어떻게 가야 가장 빠른지 또는 환승을 가장 적게 하려면 어떻게 가야 하는지 알 수 있습니다.

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