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

 
데이크스트라 알고리즘은 방향이 주어진 [[가중 그래프]](weighted graph) ''G''와 출발점 ''s''를 입력으로 받는다. 그래프 ''G''의 모든 꼭짓점들의 집합을 ''V''라 하고, [[그래프]]의 변을 출발점 ''u''와 도착점 ''v''의 [[순서쌍]] (''u'', ''v'')로 표현한다. ''G''의 모든 변들의 집합을 ''E''라 하고, 변들의 가중치는 함수 ''w'': ''E'' → [0, ∞]로 표현한다. 이때 가중치 ''w''(''u'', ''v'')는 꼭짓점 ''u''에서 꼭짓점 ''v''로 이동하는 데 드는 비용(시간, 거리 등)이 된다. 경로의 비용은 경로 사이의 모든 변들의 가중치의 합이 된다. 데이크스트라 알고리즘은 ''V''의 임의의 꼭짓점의 쌍 ''s''와 ''t''가 있을 때 ''s''에서 ''t''로 가는 가장 적은 비용이 드는 경로(최단 경로)를 찾는다. 이 알고리즘은 주어진 출발점 ''s''로부터 다른 모든 꼭짓점까지의 최단 경로를 계산하는 데도 사용할 수 있다
[[파일:Dijkstra's algorithm.svg|right|thumb|100px|예제 그래프에 대해 데이크스트라 알고리즘을 수행하는 모습. 두 개의 경감 연산을 보여주고 있다.]]
 
== 알고리즘의 개요 ==
데이크스트라 알고리즘은 각각의 꼭짓점 ''v''에 대해 ''s''에서 ''v''까지의 최단 거리 ''d''[''v'']를 저장하면서 작동한다. 알고리즘의 시작 시에 ''d''[''s'']=0이고, s가 아닌 다른 모든 꼭짓점 ''v''에 대해서는 ''d''[''v'']=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 ''d''[''v'']는 ''s''에서 ''v''까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.
경감 연산은 모든 변 (''u'', ''v'')에 대해 한번씩 경감이 적용되어 모든 ''d''[''v'']가 최단 경로의 비용을 나타내게 되었을 때 끝난다.
 
알고리즘은 과정이 끝날 때까지 꼭짓점의 집합 ''S''와 ''Q''를 저장한다. ''S''는 ''d''[''v'']가 최단 경로의 비용임이 이미 알려진 꼭짓점 ''v''의 집합이고 ''Q''는 나머지 꼭짓점들의 집합을 가리킨다. ''S''는 공집합에서 시작하여 매 단계마다 ''Q''에서 ''S''로 꼭짓점들이 하나씩 옮겨 오며, 이때 옮겨 오는 꼭짓점들은 ''d''[''u'']가 가장 낮은 값을 갖는 꼭짓점 ''u''로 정해진다. ''u''가 ''S''로 옮겨 오면, 알고리즘은 ''u''에서 시작하는 모든 변에 대해 경감 연산을 행한다.[[파일:Dijkstra's algorithm.svg|right|thumb|100px|예제 그래프에 대해 데이크스트라 알고리즘을 수행하는 모습. 두 개의 경감 연산을 보여주고 있다.]]
 
== 의사코드 ==
익명 사용자