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

잔글 (→‎설명: 중의성 해소)
:'''''참고:''' 이 문단에서는 이해를 돕기 위해서 '''교차로''', '''도로''' 그리고 '''지도'''라는 용어를 사용했지만, 공식적인 용어는 각각 '''꼭짓점''', '''변''' 그리고 '''그래프'''이다.''
 
도시의 지도에서 출발지와 목적지 사이의 가장 짧은 거리를 찾는다고 하자. 데이크스트라 알고리즘에서는 교차점마다 출발지로부터의 거리를 적어서 가장 짧은 거리를 찾는다.
도심 지도에서 ''시작점''과 ''목적지''의 두 [[교차로]] 간의 ''가장 짧은 거리''를 찾는다고 가정하자. 데이크스트라 알고리즘은 지도에 있는 다른 모든 교차로의 거리(현 위치에서)를 ''무한대''로 표시해둔다. 이 표시는 실제로 거리가 무한이라는 뜻이 아니라, 이 교차로에 가본 적이 없다는 것을 표시하기 위해서이다: 이 방법의 일부 변형은 단순히 교차로의 거리를 ''미표시'' 상태로 놔둔다. 이제 반복할 때 마다 ''현 위치''를 선택한다. 첫 번째 반복에서, 현 위치는 시작점이며, 거리(교차로의 표시)는 ''0''이다. 그 다음의 반복에서 현 위치는 시작점에서 ''가본 적 없으면서 가장 가까운 교차로''가 된다(이 교차로는 찾기 쉬울 것이다).
 
데이크스트라 알고리즘에서는 우선 모든 교차점에 ''무한대''를 적어놓는다. 이 표시는 실제 거리가 무한대라는 뜻이 아니라 교차로에 가보지 않았다는 것을 의미한다. 변형된 데이크스트라 알고리즘에서는 ''표시되지 않음''을 써놓기도 한다.
현 위치에서 직접적으로 연결된 가본 적 없는 교차로의 거리를 ''갱신''한다. 이 단계는 현 위치에서 가본 적 없는 교차로까지의 거리와 현 위치의 값을 ''더한'' 값이 현재 거리 보다 작을 때, 가본 적 없는 교차로의 [[그래프 번호매김|거리를 이 값(합)으로 바꾼다]]. 결과적으로, 그 교차로는 현 위치를 통과해 가는 경로가 이전 경로보다 짧을 경우에 거리를 바꾼다. 최단 경로를 찾기 편리하게 하려면 교차로의 거리를 붙였다면/바꿨다면, 연필로 도로에 거리를 바꾼 교차로를 향하는 화살표를 도로에 그리고 그 방향을 향하는 다른 화살표를 지운다. 모든 [[인접 (그래프 이론)|인접 교차로]]의 거리를 갱신하고 나면 현 위치를 ''방문''했다고 표시하고, 방문한 적 없는 교차로 중 (시작점에서) 가장 거리가 짧은 교차로를 선택한다. 방문 했다고 표시한 교차로는 시작점에서 가는 가장 짧은 경로가 표시되어 있을 것이며 다시 방문하거나 돌아갈 일은 없다.
 
다음으로는 모든 교차점을 표시할 때까지 반복한다. 우선 현재 위치를 정하고 시작점으로부터의 거리를 쓴다. 시작할 때의 현재 위치는 시작점이다. 그리고 시작점으로부터의 거리는 당연히 0이다.
인접한 교차로를 최단 거리로 갱신하고 현 교차로에 방문한 표시를 하고 가장 방문한 적 없는 가까운 교차로로 이동하는 과정을 목적지에 방문 표시가 될 때 까지 계속한다. 목적지에 한 번 방문 표시가 되면 (비단 목적지 뿐만 아니라 어떤 교차로에도 해당한다) 시작점에서 최단 경로가 결정되었고, ''화살표를 거슬러서 길을 되돌아갈 수 있다''. 알고리즘의 수행에서, 이 부분은(알고리즘이 목적지 노드에 도착한 이후에) 목적지 꼭짓점의 부모 노드를 쫓아 시작점으로 감으로 수행된다. 이것이 계속해서 각각의 노드의 부모 노드를 쫓아가고 있었던 이유이다.
 
그 다음 현재 위치와 연결되어있는 교차로들의 거리를 갱신한다. 현재 위치에는 시작점으로부터 가장 짧은 거리가 쓰여 있다. 현재 위치 <math>T</math>에 쓰여 있는 거리를 <math>A</math>, 이웃 교차로로 연결된 도로의 길이를 <math>B</math>, 이웃 교차로에 쓰여 있는 거리를 <math>C</math>라고 할 때, <math>A + B < C</math>이면 이웃 교차로에 '''''최단 거리는 <math>A + B</math>이며 이 값은 <math>T</math>로부터 계산되었다'''''라고 쓴다. 이 과정을 [[그래프 번호매김|완화]]라고 한다.
이 알고리즘은 모두가 예측하는 것처럼 목적지를 향해서 "조사"하려는 시도를 하지 않는다. 대신에, 다음 "현 위치"를 결정하는 유일한 고려사항은 시작점에서의 거리 뿐이다. 이 알고리즘은 따라서 시작점에서 뻗어나가기 때문에, 목적지까지 가는 최단 경로보다 짧은 거리에 있는 모든 꼭짓점을 고려한다. 이렇게 이해한다면, 알고리즘은 필연적으로 최단 경로를 찾을 수 밖에 없다. 하지만 이 특징은 데이크스트라 알고리즘의 약점 중 하나를 나타낸다: 일부 위상에서 상대적으로 느리다는 점이다.
 
현재 위치에서 연결된 모든 이웃 교차로에 대해 완화가 끝나면 현재 위치에 방문함이라고 적고 현재 위치에서 가장 가까운, 방문하지 않은 교차로로 이동한다. 방문표시가 된 교차로에는 항상 최단거리가 적혀있을 것이다. 만약 방문하지 않은 이웃 교차로가 없는 경우에는 현재 위치의 거리가 계산된 교차로로 돌아가서 가까운 방문하지 않은 교차로로 이동한다.
 
현재 위치가 목적지라면 탐색을 종료한 뒤 최단 거리를 바탕으로 최단 경로를 찾는다.
출발지를 제외한 모든 교차로에는 자신이 계산되어온 교차로가 쓰여 있을 것이다. 이 교차로를 부모 노드라고 한다. 목적지에서 부모 노드를 계속 따라가면 최단경로를 따라서 출발지에 도착하게 된다.
 
이 알고리즘은 목적지를 향해서 조사하지 않고, 목적지까지의 최단거리보다 짧은 교차로들을 모두 고려하기 때문에 최단 거리를 찾을 수 있게 된다. 하지만 모든 교차로를 고려한다는 특징으로 인해 데이크스트라 알고리즘은 특정한 지도에서 상대적으로 느리게 작동할 수 있다.
 
== 의사 코드 ==

편집

305