Dijkstra 다익스트라 알고리즘 (우선순위 큐를 사용하지 않는)

Dijkstra 다익스트라 알고리즘 (우선순위 큐를 사용하지 않는)

http://stack07142.tistory.com/47

* 다익스트라 알고리즘 (Dijkstra algorithm)

1. 개요

 : 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 

 : 다익스트라 알고리즘은 각각의 꼭짓점 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]를 새로운 값으로 바꾼다.

2. 실행 시간

 : 가장 간단한 구현으로, Q의 집합을 연결 리스트나 배열 구조로 구현하고 Extract-Min(Q) 함수를 단순한 선형 탐색으로 구현했을 때 실행 시간은 O(n^2) 시간이 된다.

만약 희소 그래프(sparse graph), 즉 n^2보다 훨씬 작은 개수의 변만을 갖는 그래프에 대해서는, 인접 리스트와 바이너리 힙 또는 피보나치 힙으로 구현한 우선순위 큐를 이용해 다익스트라 알고리즘을 더 효율적으로 구현할 수 있다. 이진 힙을 이용하면 실행 시간은 O((m+n)log n) 시간이 되고, 피보나치 힙을 통해 O((m+n)log n) 시간까지 개선할 수 있다.

3. 의사 코드

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

 1   function Dijkstra(G, w, s)
 2      for each vertex v in V[G]                        // 초기화
 3            d[v] := infinity
 4            previous[v] := undefined
 5      d[s] := 0                                                     //덮어쓰기
 6      S := empty set
 7      Q := set of all vertices
 8      while Q is not an empty set                      // 알고리즘의 실행
 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
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 != 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까지의 최단 경로 위에 있는 꼭짓점들의 목록이 된다.

출처 :https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98