Motivation
Coddy의 다익스트라 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 2번째.
다익스트라(Dijkstra) 알고리즘은 최단 거리가 이미 알려진 정점들의 집합을 확장해 나갑니다. 아직 확정되지 않은 정점 중 가장 가까운 정점을 항상 확정하며, 그 정점을 사용하여 이웃 정점들까지의 거리를 개선(완화, relax)합니다.
왜 다익스트라를 배워야 할까요?
- 어디서나 사용됨: GPS 경로 탐색, 네트워크 패킷 라우팅 및 모든 최소 비용 경로 찾기.
- 효과적인 탐욕 알고리즘(Greedy): 가중치가 음수가 아닌 한, 탐욕적인 선택이 증명 가능하게 최적해를 제공하는 명확한 예시입니다.
- 기초: 이 알고리즘의 완화(relaxation) 개념은 A* 및 기타 최단 경로 알고리즘에서 다시 등장합니다.
중요: 다익스트라는 가중치가 음수가 아니라고 가정합니다. 음수 간선이 있는 경우에는 다음 코스인 벨만-포드(Bellman-Ford) 알고리즘이 필요합니다.
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
