다익스트라 알고리즘 #다익스트라 [ 수정 내역 ] [ 수정 ]

최근 수정: 6년 전

1. 개요

Dijkstra Algorithm.

알고리즘을 만든 사람의 이름[1]을 따서 다익스트라 알고리즘이라고 한다.

2. 상세

최단 경로 알고리즘 중 하나. 그리디 방식을 사용하여 최단 경로를 계산한다. 특히, 일반적인 최단 경로 (시작점이 정해져 있고 가중치가 모두 양수일 때) 알고리즘 중에서 빠른 편에 속하며 자세한 건 최단 경로 문서를 참고 바람.

3. 구현

그리디 방식을 사용한다는 것이 가장 중요한데 시작점에서 갈 수 있는 정점 중에서 가장 가까운 정점을 차례로 탐색을 진행한다는 것이다. 구현은 의외로 간단한데, BFS 탐색을 할 줄 안다면 꽤 쉽게 구현할 수 있다. BFS는 일반적인 큐를 사용하는데 비해 다익스트라 알고리즘은 우선순위 큐를 사용한다는 점이 다르다. 우선순위 큐는 위에서 말한 것처럼 시작점에서 가장 가까운 점을 선택할 때 사용한다.

4. A* 알고리즘

다익스트라 알고리즘에 휴리스틱을 추가한 것이 A* 알고리즘이다. 자세한 건 해당 문서 참고 바람.

5. 같이 보기

최단 경로

알고리즘 프로젝트

[1] Edsger Wybe Dijkstra