최단 경로 알고리즘 (shortest path algorithm)
쉽게 풀면
최단 경로 알고리즘은 목적에 따라 여러 종류가 있다. 음의 가중치가 없다면 다익스트라 알고리즘이 효율적이고, 음의 가중치가 있다면 벨만-포드 알고리즘을 써야 하며, 모든 정점 쌍 사이의 최단 경로를 한 번에 구하고 싶다면 플로이드-워셜 알고리즘을 사용한다. 가중치가 모두 같다면 단순히 너비 우선 탐색만으로도 충분하다. 이처럼 그래프의 성질(가중치 유무, 음수 여부, 구하려는 범위)에 따라 적합한 알고리즘을 선택하는 것이 중요하다.
왜 중요한가
최단 경로 알고리즘은 내비게이션 경로 탐색, 네트워크 라우팅, 물류 최적화, 소셜 네트워크 분석 등 그래프로 표현되는 거의 모든 문제의 밑바탕이 되기 때문에 컴퓨터과학뿐 아니라 교통공학, 통신공학 논문에서도 폭넓게 인용됩니다. 새로운 응용 문제를 그래프로 모델링한 뒤 이를 효율적으로 푸는 것이 연구의 핵심 성과가 되는 경우가 많아, 기존 알고리즘을 어떻게 개선하거나 특정 조건에 맞게 변형했는지가 자주 논문의 주제로 다뤄집니다.
논문에서는 이렇게 쓰입니다
특정 상황에 맞는 최단 경로 알고리즘을 선택하고 그 근거를 제시할 때 상위 개념으로 인용된다.
이 문장은 "네트워크의 회선 상태가 계속 바뀌는 상황에서, 그때그때 상황에 맞는 최적 경로를 다시 찾아내는 알고리즘을 통신망 라우팅에 적용했다"는 뜻으로, 네트워크공학 연구에서 흔히 쓰이는 표현입니다.
이 문장은 "도로를 그래프 형태로 바꾼 뒤, 목적지 방향을 미리 어림잡아 탐색 속도를 높이는 A* 알고리즘으로 실시간 교통 상황까지 고려한 최적 경로를 찾았다"는 뜻입니다.
조금 더 깊게 보면
최단 경로 알고리즘들은 대부분 "완화(relaxation)"라는 공통 연산, 즉 어떤 정점까지의 현재까지 알려진 최단 거리를 인접 간선을 통해 갱신할 수 있는지 반복적으로 확인하는 원리에 기반합니다. 다익스트라 알고리즘은 이 과정을 거리순으로 정렬된 우선순위 큐를 이용해 효율화한 것이고, A* 알고리즘은 여기에 목적지까지의 예상 거리(휴리스틱)를 더해 탐색 범위를 줄인 변형입니다. 그래프의 크기가 매우 크거나 실시간으로 변하는 경우에는 정확한 최적해 대신 근사해를 빠르게 구하는 방법이 쓰이기도 합니다.
주의할 점
어떤 최단 경로 알고리즘을 쓸지는 그래프에 음의 가중치가 있는지, 음의 사이클이 있는지, 구하려는 것이 단일 시작점 최단 경로인지 전체 쌍 최단 경로인지에 따라 달라진다.