+ 이 글은 작성자가 직접 공부하고 복습하며 작성한 글입니다. 만약 직접 작성하지 않았다면, 꼭 출처를 밝히겠습니다!
+ 이 글은 개인적인 공부를 바탕으로 작성되었기에, 틀린 부분이 있을 수 있으며, 틀린 부분이 있다면 알려주시면 감사하겠습니다!
+ 이 글을 다른 곳으로 가져가신다면, 꼭 출처를 남겨주세요~
+ '참고사이트'는 공부하기 위해 참고한 사이트들을 모아 둔 것입니다.
+ 혹시라도 문제가 된다면 바로 조취를 취할테니, 말해주시면 감사하겠습니다!
최간거리 찾기 알고리즘 중, 유명한 다익스트라 알고리즘을 정리해봅니다!
[ 다익스트라 알고리즘(Dijkstra Algorithm) ]
+ 음의 가중치가 없는 그래프에서 한 정점에서 다른 정점까지의 모든 최단거리를 구하는 알고리즘입니다.
+ '순차적(일반)' 과 '우선순위 큐', 두 가지 방법으로 나타낼 수 있습니다.
[ 조건 ]
+ 음의 가중치가 없어야 합니다.
+ 알고리즘 시작 시, 시작 점에서 모든 점까지의 거리는 Inf(Infinity,무한대)로 설정합니다.
[ 기본 로직 ]
+ 시작 정점을 기준으로 연결된 모든 정점들을 까지의 가중치를 비교해가며, 최단거리를 갱신합니다.
+ 시작 정점에서 각 정점까지의 최단거리를 저장하는 배열(Distance)을 만듭니다.
+ "현재 정점에서 가지고 있는 최단거리 vs 다른 정점에서 현재 정점까지 계산한 최단거리" 를 계산해서 최단 거리를 Update합니다.
+ 위의 비교에서 '기존의 최단거리'가 더 짧으면 연산을 하지 않습니다.
+ 다음 정점을 선택 시, 방문하지 않은 정점 중, 가장 짧은 거리의 정점을 선택해서 계산합니다.
[ 순차적(일반) 알고리즘 ]
+ 먼저, 예시 그래프를 하나 준비합니다. 시작 정점은 '5'번 입니다.
+ 아무런 작업을 하지 않았기에 모든 정점과의 거리는 Inf(Infinity, 무한대)입니다.
+ 시작 정점을 기준으로 시작해보면,
1) 5번과 연결된 정점은 2,4번입니다.
2) 각각의 정점과의 최단거리를 비교합니다.
3) 2번 = Min(기존 최단거리, 이전 정점까지의 최단거리 + 현재 정점까지의 거리) -> Min(Inf, 0+4) = 4
4) 4번 = Min(기존 최단거리, 이전 정점까지의 최단거리 + 현재 정점까지의 거리) -> Min(Inf, 0+2) = 2
+연산이 끝나고나면 그래프가 Update됩니다.
+ 5번 정점과 연결된 정점 중, 탐색하지 않았고, 가장 짧은 정점 4번을 탐색합니다.
1) 4번과 연결된 정점은 2,3번입니다.
2) 각각의 정점과 최단거리를 비교합니다.
3) 2번 = Min(기존 최단거리, 이전 정점까지의 최단거리 + 현재 정점까지의 거리) -> Min(4, 2+1) = 3
4) 3번 = Min(기존 최단거리, 이전 정점까지의 최단거리 + 현재 정점까지의 거리) -> Min(Inf, 2+1) = 3
+ 연산이 끝나고나면 그래프가 Update됩니다.
+ 방문하지 않은 정점 중, 가장 짧은 거리의 정점이 2번이므로 2번부터 계산합니다.
+ 이와 같은 연산을 끝까지 하고나면 모든 점까지의 최단거리를 구할 수 있습니다.
[ 우선순위 큐(힙구조) 알고리즘 ]
+ 우선순위 큐를 이용한 방식의 알고리즘은 '우선순위 큐'를 이용해 항상 최소거리의 정점을 우선적으로 계산하는 알고리즘입니다.
+ 위의 순차적 알고리즘에 비해 더욱 빠른 연산이 가능합니다. 왜나하면 최소 힙을 이용하여 더욱 빠르게 최소거리의 정점(다음 탐색할 곳)을 찾을 수 있기 때문입니다.
+ 우선순위를 이용하면, 최소거리부터 계산하게되어 미리 최단거리를 구할 수 있어, 차후 불필요한 연산을 줄일 수 있습니다.
+ 일반적인 구조는 순차적 알고리즘과 동일하며, 우선순위 큐를 쓴다는 점만 다릅니다.
1) 우선순위 큐에서 Pop합니다.
2) 방문한 곳인지 확인합니다. 방문하지 않았으면 방문한 곳으로 표시합니다.
3) 현재 정점(A)의 최소거리와 비교합니다. Min(기존 최소거리, 이전 정점 최소거리 + distance)
4) 기존 최소거리가 더 작으면 연산을 하지않고, 그렇지 않으면 연산합니다.
5) 연산하게 되면, 현재 정점(A)과 연결된 정점(B) 중, 기존 최소거리(B)보다 작아지는 정점들을 큐에 집어 넣습니다. Min(기존 최소거리(B), 이전 정점 최소거리(A) + distance)
+ 순차적 알고리즘보다 빠른 연산이 가능합니다!
- 자세한 시간복잡도 비교는 나중에...
*** 참고해야할 점
- 가중치가 음수인 경우에는 벨만-포드 알고리즘을 사용해야 합니다.
- 다익스트라 알고리즘은 항상 최소거리를 우선으로 연산하기 때문에, 한 정점을 두 번 지나는 최소거리는 나오지 않습니다.(왜나햐면 그 지점을 지나가면 무조건 최소거리보다 많이 나오기 때문입니다.)
Q. 왜 탐색한 곳을 표시해서 나중에 계산하지 않나요? 나중에 다른 루트를 통해 더욱 짧은 거리가 생길 수 있지 않나요??
A. 최단거리를 최우선으로 연산하기 때문에, 이미 방문한 점을 재 방문한 루트는 무조건 기존의 루트보다 거리가 클 수 밖에 없습니다. 그러니 비교 연산 조차 해 줄 필요가 없습니다.
[Code]
+ https://www.acmicpc.net/problem/1753의 문제 풀이과정을 사용했습니다.
** 참고사이트 **
- http://hsp1116.tistory.com/42
- https://www.zerocho.com/category/Algorithm/post/584bd46f580277001862f1af
Copyright © -강정이좋아- 무단 전재 및 재배포는 하지 말아주세요.
'요리 레시피 > Algorithm' 카테고리의 다른 글
| [자료구조] Union-Find, 유니온파인드 (0) | 2018.10.22 |
|---|---|
| [BaekJoon] 이항계수, 페르마의 소정리, 거듭제곱 feat.11401번(이항계수3) (0) | 2018.05.12 |
| [DFS][BFS] DFS 와 BFS (0) | 2018.03.27 |
| [Dp] DP에서 배열 사용 (0) | 2018.03.26 |
| [BackJoon] 충격의 N-Queen 문제 feat.9663번(N-Queen) (0) | 2018.03.26 |