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

 
== 알고리즘의 개요 ==
데이크스트라 알고리즘은 각각의 꼭짓점 ''v''에 대해 ''s''에서 ''v''까지의 최단 거리 ''d''[''v'']를 저장하면서 작동한다. 알고리즘의 시작 시에 ''d''[''s'']=0이고, 값은s가 아닌 다른 모든 꼭짓점 ''sv''에 대해서는 0이고, (''d''[''sv'']=0) 다른 모든 꼭짓점에 대해서는 무한대(∞) 값으로∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 ''d''[''v'']는 ''s''에서 ''v''까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.
 
데이크스트라 알고리즘은 '''변 경감'''('''edge relaxation''')이라고 불리는 기본 연산을 바탕으로 한다. ''s''에서 ''u''까지의 최단 경로(''d''[''u''])를 이미 알고 있고, ''u''에서 ''v''까지 길이가 ''w''(''u'',''v'')인 변 (''u'', ''v'')가 존재할 때, ''s''에서 ''v''까지의 최단 경로는 ''u''까지의 최단 경로에 변 (''u'', ''v'')를 연장함으로써추가함으로써 얻을 수 있다. 이 경로의 비용은 ''d''[''u'']+''w''(''u'', ''v'')가 되며, 이 비용이 현재의 ''d''[''v''] 값보다 낮으면 ''d''[''v'']를 새로운 값으로 바꾼다.
 
경감 연산은 모든 변 (''u'', ''v'')에 대해 한번씩 경감이 적용되어 모든 ''d''[''v'']가 최단 경로의 비용을 나타내게 되었을 때 끝난다.