정의 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘 알고리즈 개요 데이크스트라 알고리즘은 각각의 꼭짓점 v에 대해 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 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]가 최단 경로의 비용을 나타내게 되었을 때 끝난다. 실행시간 개의 변과 {\displaystyle n} 개의 꼭짓점 을 가진 그래프 에 대해 대문자 O 표기법 으로 데이크스트라 알고리즘의 실행시간을 나타낼 수 있다. 가장 간단한 구현으로, Q 의 집합을 연결 리스트 나 배열 구조로 구현하고 Extract-Min(Q) 함수를 단순한 선형 탐색 으로 구현했을 때 실행 시간은 {\displaystyle O(n^{2})} 시간이 된다. 만약 희소 그래프(sparse graph), 즉 {\displaystyle n^{2}} 보다 훨씬 작은 개수의 변만을 갖는 그래프에 대해서는, 인접 리스트 와 바이너리 힙 또는 피보나치 힙 으로 구현한 우선순위 큐 를 이용해 데이크스트라 알
댓글
댓글 쓰기