최단 경로 알고리즘
최단 경로 문제?
두 노드를 잇는 가장 짧은 경로를 찾는 문제
가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 함이 최소가 되도록 하는 경로를 찾는 것이 목적
최단 경로 문제 종류
- 단일 출발 (single-source) 최단 경로 문제
- 그래프 내의 특정 노드 u에서 출발해, 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제
- 단일 도착 (single-destination) 최단 경로 문제
- 모든 노드들로부터 출발해, 그래프 내의 특정 노드 u로 도착하는 가장 짧은 경로를 찾는 문제
- 단일 쌍 (single-pair) 최단 경로 문제
- 주어진 노드 u와 v간의 최단 경로를 찾는 문제
- 전체 쌍 (all-pair) 최단 경로 문제
- 그래프 내의 모든 노드 쌍 (u,v) 사이에 대한 최단 경로를 찾는 문제
최단 경로 알고리즘 - 다익스트라 알고리즘
다익스트라 알고리즘은 위의 최단 경로 문제 종류 중 1번에 해당
하나의 정점에서 다른 모든 정점에 도착하는 가장 짧은 거리를 구하는 문제
다익스트라 알고리즘 로직
- 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며 최단 거리를 갱신하는 기법
- 다익스트라 알고리즘은 너비우선탐색 (BFS)와 유사
- 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트
- 우선순위 큐를 활용한 다익스트라 알고리즘
- 우선순위 큐는 MinHeap 방식을 활용해서 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼냄
- 첫 정점을 기준으로 배열을 선언해 각 정점까지의 거리를 저장
- 초기 첫 정점의 거리는 0, 나머지는 무한대로 저장함 (inf 라고 표현)
- 우선순위 큐에 (첫 정점 거리 0) 만 먼저 넣음
- 우선순위 큐에서 노드를 꺼냄
- 첫 정점이 꺼내짐
- 첫 정점에서 인접한 노드들 각각에 대해 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교
- 배열에 저장되어 있는 거리보다 첫 정점에서 해당 노드로 가는 거리가 더 짧은 경우, 배열에 해당 노드의 거리를 업데이트 함
- 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣음
- 결과적으로 너비 우선 탐색 방식과 유사하게 첫 정점에 인접한 노드들을 순차적으로 방문하게됨
- 배열에 기록된 현재까지 발견된 가장 짧은 거리보다 더 긴 거리 (루트)를 가진 (노드, 거리)의 경우, 해당 노드와 인접한 노드간의 거리 계산을 하지 않음
- 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복
- 첫 정점을 기준으로 배열을 선언해 각 정점까지의 거리를 저장
- 우선순위 큐는 MinHeap 방식을 활용해서 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼냄
예제로 이해하는 다익스트라 알고리즘 (우선순위 큐 활용)
1단계: 초기화
- 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
- 초기에는 첫 정점의 거리는 0, 나머지 무한대로 저장 (inf)
- 우선순위 큐에 (첫 정점 거리 0) 만 먼저 넣음
2단계: 우선순위 큐에서 추출한 (A, 0) [노드, 첫 노드와의 거리] 를 기반으로 인접한 노드와의 거리 계산
- 우선순위 큐에서 노드를 꺼냄
- 첫 정점이 꺼내짐
- 첫 정점에서 인접한 노드들에 대해 각 노드로 가는 거리와 현재 배열에 저장되어 있는 거리를 비교
- 배열에 저장되어 있는 거리보다 거리가 더 짧을 경우 배열에 해당 노드의 거리를 업데이트
- 배열에 해당 노드의 거리가 업데이트된 경우 우선순위 큐에 넣음
- 결과적으로 너비 우선 탐색 방식과 유사하게 첫 정점에서 인접한 노드들을 순차적으로 방문하게 됨
- 만약, 배역에 기록된 현재까지 발견된 가장 짧은 거리보다 더 긴 거리 (루트)를 가진 (노드, 거리)의 경우에는 해당 노드와 인접한 노드간의 거리 계산을 하지 않음
3단계: 우선순위 큐에서 (C, 1) [노드, 첫 노드와의 거리] 를 기반으로 인접한 노드와의 거리 계산
- 우선순위 큐가 MinHeap (최소 힙) 방식이므로, 위 표에서 넣어진 (C, 1), (D, 2), (B, 8) 중 (C, 1)이 먼저 추출 (pop)
- 1단계까지의 A - B 최단 거리는 8인 상태
- A - C 까지의 거리는 1, C에 인접한 B, D 에서 C - B는 5 즉, A - C - B는 1 + 5 = 6 이므로, A - B 최단 거리 8보다 더 작은 거리를 발견, 이를 배열에 업데이트
- 배열에 업데이트했으므로 B, 6 (A에서 B까지의 최단 거리) 값이 우선순위 큐에 넣어짐
- C - D 의 거리는 2 즉, A - C - D는 1 + 2 = 3이므로, A - D의 현재 최단 거리인 2보다 긴 거리, 그래서 D의 거리는 업데이트 되지 않음
- A - C 까지의 거리는 1, C에 인접한 B, D 에서 C - B는 5 즉, A - C - B는 1 + 5 = 6 이므로, A - B 최단 거리 8보다 더 작은 거리를 발견, 이를 배열에 업데이트
4단계: 우선순위 큐에서 (D, 2) [노드, 첫 노드와의 거리]를 기반으로 인접한 노드와의 거리 계산
- 지금까지 접근하지 못했던 E와 F 거리가 계산됨
- A - D 까지의 거리인 2에 D - E가 3이므로 이를 더해서 E, 5
- A - D 까지의 거리인 2에 D - F가 5이므로 이를 더해서 F, 7
5단계: 우선순위 큐에서 (E, 5) [노드, 첫 노드와의 거리] 를 기반으로 인접한 노드와의 거리 계산
- A - E거리가 5인 상태에서 E에 인접한 F를 가는 거리는 1로 A - E - F는 5 + 1 = 6, 현재 배열에 A - F 최단거리가 7로 기록되어 있으므로 F, 6으로 업데이트
- 우선순위 큐에 F, 6 추가
6단계: 우선순위 큐에서 (B, 6), (F, 6)를 순차적으로 꺼내 각 노드 기반으로 인접한 노드와의 거리 계산
- 예제의 방향 그래프에서 B노드는 다른 노드로 가는 루트가 없음
- F노드는 A노드로 가는 루트가 있으나 현재 A - A 가 0인 반면, A - F - A는 6 + 5 = 11이므로 더 긴 거리이기때문에 업데이트 되지 않음
6단계: 우선순위 큐에서 (F, 7), (B, 8)를 순차적으로 꺼내 각 노드 기반으로 인접한 노드와의 거리 계산
- A - F로 가는 하나의 루트의 거리가 7인 상황이지만, 배열에서 이미 A - F로 가는 현재의 최단 거리가 6인 루트의 값이 있는 상황이므로 더 긴 거리인 F, 7루트 기반 인접 노드까지의 거리는 계산할 필요가 없음, 그래서 계산없이 스킵함계산하더라도 A - F 거리가 6인 루트보다 무조건 더 긴거리가 나올 수 밖에 없음계산하더라도 A - F 거리가 6인 루트보다 무조건 더 긴거리가 나올 수 밖에 없음
- 계산하더라도 A - F 거리가 6인 루트보다 무조건 더 긴거리가 나올 수 밖에 없음
- B, 8 도 현재 A - B 거리가 6이므로, 인접 노드 거리 계산이 필요 없음
우선순위 큐 사용시 장점
- 가장 짧은 거리의 노드에 대해서 먼저 계산됨
- 더 긴 거리의 계산에 대해서 스킵할 수 있음
feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스
'코테 > 알고리즘' 카테고리의 다른 글
탐욕 알고리즘 (0) | 2023.09.12 |
---|---|
너비 우선 탐색 (BFS) (0) | 2023.09.05 |
그래프 이해 (0) | 2023.09.04 |
동적 계획법과 분할 정복 (0) | 2023.08.30 |
재귀 호출 (0) | 2023.08.30 |