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

잔글
봇: 틀 이름 및 스타일 정리
잔글 (봇: 날짜 변수 정리)
잔글 (봇: 틀 이름 및 스타일 정리)
 
== 알고리즘 ==
[[파일:Dijkstras progress animation.gif|thumb섬네일|[[로봇공학|로봇]] [[모션 계획]] 문제에서 데이크스트라 알고리즘이 시작점(좌측 하단, 빨간색)에서 도착점(우측 상단, 초록색)까지의 경로를 찾는 도해. 빈 꼭짓점은 "시험" 집합("미방문" 꼭짓점들의 집합)을 나타낸다. 채워진 꼭짓점은 방문한 꼭짓점으로, 색은 거리를 나타낸다: 초록색이 될 수록 더 가깝다는 의미이다. 다른 방향으로 있는 꼭짓점들은 균일하게 탐색되며, 데이크스트라 알고리즘이 [[균일 휴리스틱|휴리스틱]]을 0과 같게 사용하기 때문에 원형 [[파면]]으로 적거나 많게 나타난다.]]
 
시작할 꼭짓점은 '''초기점'''으로, '''꼭짓점 ''Y''의 거리'''를 '''초기점'''에서 ''Y''까지의 거리로 정의한다. 데이크스트라 알고리즘은 초기 거리 값을 부여하고, 단계를 거듭하며 개선시킬 것이며, 이 개선시키는 것을 '''변 경감'''('''edge relaxation''')이라고 한다.
 
다음 알고리즘에서, 코드 {{모노|u ← vertex in ''Q'' with min dist[u]}}는 꼭짓점 집합 {{모노|<var>Q</var>}}에서 가장 작은 {{모노|dist[<var>u</var>]}} 값을 가지는 꼭짓점 {{모노|<var>u</var>}}를 찾는다. {{모노|length(<var>u</var>, <var>v</var>)}}는 두 인접한 꼭짓점인 {{모노|<var>u</var>}}와 {{모노|<var>v</var>}}를 연결하는 변의 길이 (둘 간의 거리)를 반환한다. 18번째 줄의 변수 {{모노|<var>alt</var>}}는 루트 꼭짓점에서 {{모노|<var>u</var>}}를 통해서 인접 꼭짓점 {{모노|<var>v</var>}}까지 가는 경로의 길이이다. 이 경로가 현재 {{모노|<var>v</var>}}에 대해서 기록된 최단 경로보다 짧다면, 현재 경로를 이 {{모노|<var>alt</var>}} 경로로 대체한다. {{모노|prev}} 배열은 소스까지 최단 경로를 찾기 위한 소스 그래프의 "다음" 꼭짓점을 나타내는 배열이다.
[[파일:DijkstraDemo.gif|thumb섬네일|유클리드 거리에 기반한 데이크스트라 알고리즘의 시연이다. 빨간색 선은 최단 경로이다. 다시 말해, ''u''와 [''u'']를 연결하는 선이다. 파란 선은 변 경감이 이루어지는 위치를 나타낸다. 즉, ''v''와 ''Q''에 있는 꼭짓점 ''u''를 연결하는 선으로, 소스에서 ''v''까지 가는 더 짧은 경로를 나타낸다.]]
 
1 '''function''' Dijkstra(''Graph'', ''source''):

편집

1,378,870