다익스트라 알고리즘 (Dijkstra's Algorithm)

한 줄 정의: 길마다 비용(가중치)이 다른 그래프에서, 한 지점에서 다른 모든 지점까지 가장 비용이 적게 드는 경로를 찾아내는 알고리즘입니다.

쉽게 풀면

내비게이션이 출발지에서 목적지까지 최단 경로를 찾는 과정과 비슷합니다. 다익스트라 알고리즘은 출발점에서 가장 가까운 곳부터 하나씩 확정해 나가면서, 그곳을 거쳐 갈 수 있는 다음 지점까지의 거리를 갱신합니다. 이렇게 "지금까지 알려진 것 중 가장 가까운 곳"을 반복해서 확정해 나가면, 결국 출발점에서 모든 지점까지의 최단 거리를 구할 수 있습니다. 단, 길의 비용(거리, 시간 등)이 음수가 아니어야 정확하게 동작합니다.

왜 중요한가

다익스트라 알고리즘은 최단 경로 문제라는 그래프 이론의 가장 기본적인 문제를 효율적으로 해결하는 표준 방법이기 때문에, 교통·물류 경로 탐색부터 통신망 라우팅, 게임의 길찾기(pathfinding)에 이르기까지 폭넓은 응용 논문에서 배경 알고리즘으로 인용됩니다. 또한 이후 등장한 A* 알고리즘 등 더 발전된 탐색 기법들이 다익스트라를 기반으로 확장되었기 때문에, 관련 알고리즘 연구의 출발점으로도 자주 언급됩니다.

논문에서는 이렇게 쓰입니다

"실제 도로망 데이터에서 두 지점 간 최단 이동 경로와 소요 시간을 계산하기 위해 다익스트라 알고리즘(Dijkstra's algorithm)을 적용하였다."

이 문장은 도로나 네트워크처럼 구간마다 이동 비용이 다른 지도 데이터에서, 특정 출발지로부터 다른 모든 지점까지의 최단 경로와 거리를 다익스트라 알고리즘으로 계산했다는 뜻입니다. 경로 탐색, 교통망 분석, 네트워크 라우팅을 다루는 논문에서 자주 사용됩니다.

"통신 네트워크의 링크 비용을 반영한 그래프에서 다익스트라 알고리즘을 이용해 각 노드 간 최소 지연 경로를 산출하였다."

네트워크 라우팅 분야에서는 링크의 지연 시간이나 대역폭을 비용으로 설정한 뒤, 다익스트라 알고리즘으로 데이터가 거쳐야 할 최적 경로를 계산하는 방식이 자주 사용됩니다.

"게임 맵의 지형 이동 비용을 가중치로 하는 그래프를 구성하고, 다익스트라 알고리즘을 통해 NPC의 최적 이동 경로를 계산하였다."

게임 인공지능·경로 탐색 분야에서는 지형에 따라 이동 비용이 달라지는 상황에서 다익스트라 알고리즘을 기반으로 한 길찾기 기법이 널리 활용됩니다.

조금 더 깊게 보면

다익스트라 알고리즘의 성능은 아직 확정되지 않은 노드 중 최소 거리 노드를 얼마나 빨리 찾아내는지에 좌우되며, 이를 위해 흔히 우선순위 큐와 힙를 사용해 시간복잡도를 개선합니다. 목적지가 정해져 있는 경우에는 목적지 방향으로 탐색을 유도하는 휴리스틱을 추가한 A* 알고리즘이 더 효율적인 대안으로 쓰이기도 합니다. 논문에서 다익스트라를 언급할 때는 그래프의 크기와 밀도, 사용한 자료구조(배열인지 힙인지)에 따라 실제 수행 시간이 크게 달라질 수 있다는 점을 함께 확인하는 것이 좋습니다.

주의할 점

다익스트라 알고리즘은 간선의 가중치가 음수인 경우에는 올바른 결과를 보장하지 않는다는 점을 놓치기 쉽습니다. 음수 가중치가 있는 그래프에서는 벨만-포드 알고리즘 같은 다른 방법을 써야 하며, 단순히 그래프를 어떤 순서로 방문할지만 다루는 그래프 순회와 달리 다익스트라는 "가장 저렴한 경로"라는 최적화 목표를 함께 고려한다는 차이도 있습니다.