Algorithm Dijkstra(데이크스트라) 최단경로 알고리즘

Dijkstra(데이크스트라) 최단경로 알고리즘

Home

Contact

알고리즘의 개요

• 방향이 주어진 가중 그래프(weighted graph) G와 출발점 s(tart)를 입력으로 받는다.
• V(ertex) : 그래프의 모든 점들의 집합
• (u(ndefined), v(ertex)) : 그래프의 간선. 간선의 출발점 u, 간선의 도착점 v
• E(ddge) : G의 모든 간선들의 집합
• w: E -> [0, infinity] : 간선들의 가중치
• w(u, v): 점 u에서 점 v로 이동하는데 드는 비용.
• 경로의 비용 : 경로 사이의 모든 간선들의 가중치의 합.
• 데이크스트라 알고리즘은 V의 임의의 점의 쌍 s 와 t가 있을 때 s 에서 t 로 가는 가장 적은 비용이 드는 경로(최단경로) 를 찾는다.
• 시작점을 제외한 다른 정점이 모두 시작점을 가리킨다고 가정.
• 직접 연결되어 있지 않은 정점은 무한대의 비용임.
• A-C 간선의 비용이 A - B, A - C 의 비용보다 크다면 C는 B를 가리키도록 한다.

데이크스트라 알고리즘은 각각의 꼭짓점 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]가 최단 경로의 비용을 나타내게 되었을 때 끝난다. 알고리즘은 과정이 끝날 때까지 꼭짓점의 집합 S와 Q를 저장한다. S는 d[v]가 최단 경로의 비용임이 이미 알려진 꼭짓점 v의 집합이고 Q는 나머지 꼭짓점들의 집합을 가리킨다. S는 공집합에서 시작하여 매 단계마다 Q에서 S로 꼭짓점들이 하나씩 옮겨 오며, 이때 옮겨 오는 꼭짓점들은 d[u]가 가장 낮은 값을 갖는 꼭짓점 u로 정해진다. u가 S로 옮겨 오면, 알고리즘은 u에서 시작하는 모든 변에 대해 경감 연산을 행한다.

아래 알고리즘 의사코드에서 u := Extract_Min(Q)는 꼭짓점의 집합 Q에서 가장 작은 d[u]값을 찾은 다음 그 꼭짓점 u를 Q에서 제거한 후 반환하는 함수를 가리킨다.

 1   function Dijkstra(G, w, s)
 2      for each vertex v in V[G]                        // 초기화  모든 점들의 집합V[G]원소인 도착점v들에 데하여 
 3            d[v] := infinity                           // 모든 경로의 비용을 무한대로 설정한다.
 4            previous[v] := undefined                   // 바로 앞의 꼭지점 위치를 간선의 출발점으로 한다..
 5      d[s] := 0                                        // 출발점의 비용을 0으로 초기화 한다.
 6      S := empty set                                   // 출발점 비용을 비운다.
 7      Q := set of all vertices                         // Q에 방문하지 않은 모든 꼭지점들을 담는다.
 8      while Q is not an empty set                      // Q의 꼭지점들이 다 비워질 때 까지 알고리즘의 실행
 9            u := Extract_Min(Q)                        // 집합 Q에서 d[u]가 최소인 u를 찾아 빼냄
10           S := S union {u}                            // 빼낸 u를 S에 삽입
11           for each v with edge (u,v) defined          // (u, v)에 인접한 도착점 v 만큼 반복
12                  if d[v] > d[u] + w(u,v)              //(간선의 출발점의 비용 +간선의 도착점의 비용)이 도착점의 비용보다 작다면
13                        d[v] := d[u] + w(u,v)          // 변(u,v)의 경감. 도착점의 비용은 (간선의 출발점의 비용 +간선의 도착점의 비용)
14                        previous[v] := u               //경로 추적할 때 쓰임
    		

만약 s에서 모든 v에 까지의 최소 경로를 찾는 것이 아니라, s에서 특정 꼭짓점 t까지의 최단 거리만을 알고 싶다면 8번째 행에 u\neq t의 조건을 추가하면 된다.

previous[]가 구해지면, 이를 이용해 다음과 같이 s에서 t까지의 최단 경로를 얻을 수 있다.

1 S := empty sequence 
2 u := t
3 while defined u                                        
4       insert u to the beginning of S
5       u := previous[u]
	

이제 S는 s에서 t까지의 최단 경로 위에 있는 꼭짓점들의 목록이 된다.

참고문헌:위키피디아

© Copyright by joonserver