"데이크스트라 알고리즘"의 두 판 사이의 차이

잔글
→‎알고리즘: 책<<알고리즘 문제해결전략>>에 나오는 용어로 수정
잔글 (→‎실행 시간: 내용 다듬기)
잔글 (→‎알고리즘: 책<<알고리즘 문제해결전략>>에 나오는 용어로 수정)
[[파일:Dijkstras progress animation.gif|섬네일|[[로봇공학|로봇]] [[모션 계획]] 문제에서 데이크스트라 알고리즘이 시작점(좌측 하단, 빨간색)에서 도착점(우측 상단, 초록색)까지의 경로를 찾는 도해. 빈 꼭짓점은 "시험" 집합("미방문" 꼭짓점들의 집합)을 나타낸다. 채워진 꼭짓점은 방문한 꼭짓점으로, 색은 거리를 나타낸다: 초록색이 될 수록 더 가깝다는 의미이다. 다른 방향으로 있는 꼭짓점들은 균일하게 탐색되며, 데이크스트라 알고리즘이 [[균일 휴리스틱|휴리스틱]]을 0과 같게 사용하기 때문에 원형 [[파면]]으로 적거나 많게 나타난다.]]
 
시작할 꼭짓점은 '''초기점'''으로, '''꼭짓점 ''Y''의 거리'''를 '''초기점'''에서 ''Y''까지의 거리로 정의한다. 데이크스트라 알고리즘은 초기 거리 값을 부여하고, 단계를 거듭하며 개선시킬 것이며, 이 개선시키는 것을 '''간선 경감완화'''('''edge relaxation''')이라고 한다.
 
# 모든 꼭짓점을 미방문 상태로 표시한다. ''미방문 집합''이라는 모든 미방문 꼭짓점의 집합을 만든다.

편집

305