다익스트라 알고리즘(Dijkstra's Algorithm)
하나의 출발점에서 나머지 모든 지점까지의 최단 경로를, 거리나 비용처럼 가중치가 있는 그래프에서 매 단계마다 가장 가까운 지점을 확정해나가는 방식으로 체계적으로 찾아내는 대표적인 경로 탐색 알고리즘입니다.
한눈에 보는 정의
다익스트라 알고리즘(Dijkstra's Algorithm)은 하나의 출발점에서 나머지 모든 지점까지의 최단 경로를, 가중치가 있는 그래프에서 체계적으로 찾아내는 대표적인 경로 탐색 알고리즘입니다.
자세히 알아보기
- 예문: "내비게이션 앱은 도로망을 그래프로 표현한 뒤, 다익스트라 알고리즘과 비슷한 방식으로 최단 경로를 계산해 안내한다."
- 출발점에서 가장 가까운 지점부터 하나씩 확정해나가면서, 그 지점을 거쳐 갈 수 있는 다음 지점들까지의 거리를 갱신하는 과정을 반복해, 결국 모든 지점까지의 최단 거리를 찾아냅니다.
- OSPF(개방형 최단 경로 우선 프로토콜) (OSPF) 같은 라우팅 프로토콜은 네트워크를 그래프로 보고, 각 라우터가 자신을 기준으로 다익스트라 알고리즘을 돌려 다른 모든 네트워크까지의 최단 경로를 계산합니다.
- 길의 거리가 음수인 경우는 다룰 수 없다는 제약이 있지만, 실제 네트워크나 도로의 거리·비용은 음수가 될 수 없어 이 알고리즘이 실무에서 폭넓게 활용됩니다.