Directed Acyclic Graph(DAG)
DAG란 그래프 연결에 방향이 있고(Directed), 한 곳에서 순환이 발생하지 않는(Acyclic) 그래프(Graph)를 의미합니다.
Edge Relaxation
DAG Shortest Path 문제를 풀기 위해 Edge Relaxation 개념이 필요합니다. Edge Relaxation이란, 가중치가 있는 그래프(Weighted Graph)에서, 각 edge에 배정되어 있는 만큼의 가중치를 더해가며 탐색할 때, 더 나은(작은) 경로의 가중치가 있다면 그 값으로 update하는 것을 의미합니다. 말이 어렵게 느껴지는데 굉장히 쉬운 개념입니다. 결국 더 나은 대안으로 수정한다는 의미입니다. 그리고 앞으로 그래프에서 이 작업을 Relax라고 부릅니다.
그림으로 보면 다음과 같습니다.
- (a): 기존에 어떠한 다른 경로에 의해 v가 9의 값을 가지게 되었습니다. 하지만, v까지 가는 경로 중 u에서 v로 가는 경로를 선택한다면 5+2=7의 값으로 v의 값을 수정해줄 수 있습니다. 9보다 7이 더 나은(작은) 경로이므로, Relax를 거치면 v의 값은 7로 수정됩니다.
- (b): 기존에 어떠한 다른 경로에 의해 v가 6의 값을 가지게 되었습니다. 이때 u를 거쳐 v로 가게 방식은 5+2=7로, 기존의 6보다 나은(작은) 대안이 아닙니다. 따라서 Relax를 거쳐도 v는 그대로 6의 값을 갖습니다.
Edge Relaxation의 코드는 다음과 같습니다. 여기서 ".d"는 시작점(root node)로부터의 distance를 말합니다.
- 만약 v까지의 거리가 u까지의 거리에 (u,v) edge의 가중치를 더한 것보다 크면,
- v.d를 더 작은 값으로 업데이트한다.
DAG Shortest Path
DAG 그래프의 최단경로를 찾는 문제입니다. DAG Shortest Path는 Topological Sort와 Edge Relaxation을 이용하여 구할 수 있습니다. Topological Sort에 대한 내용은 아래 글에서 확인하실 수 있습니다.
[알고리즘] 위상 정렬(Topological Sort)
Topological Sort는 기본적으로 DFS를 통해 구현합니다. DFS에 대한 내용은 아래 글에 있습니다. https://stevenkim1217.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-
stevenkim1217.tistory.com
DAG Shortest Path를 찾는 Pseudo Code는 아래와 같습니다.
- 우선 DAG에서 Topological Sort를 수행한 후,
- 모든 vertex에 대해 Relaxation을 수행해준다.
이 코드를 통해 DAG의 Shortest Path를 구할 수 있습니다.
Visualization
DAG Shortest Path의 과정을 시각화하면 다음과 같습니다.
- 우선 왼쪽에서 오른쪽 방향으로 Topological Sort를 수행합니다. 이 정렬된 방향(왼→오)으로 순회를 수행합니다.
- (a): 시작 노드가 s이므로, s는 0으로, 나머지는 ∞로 초기화합니다.
- (b): r은 무한대의 값을 가지므로, 연결된 vertices에 5나 3을 더해도 무한대이다. 아주 큰 값을 가지므로 relax를 거쳐도 연결된 vertices들의 값이 업데이트 되지 않습니다.
- (c): s는 0이므로 무한대의 값을 가지고 있는 t와 x의 값을 업데이트 해줄 수 있습니다. 0+2<∞ 이고 0+6<∞ 이므로, t와 x의 값을 각각 2와 6으로 relax 해줍니다.
- (d): 같은 방식으로 relax 해줍니다.
- (e): 이때, 6의 값을 가지고 있던 기존의 y보다 x(6)에서 -1을 더한 값인 5가 더 작으므로 y의 값을 relax해줍니다.
이런 방식으로 Topological 방향으로 Relaxation을 수행하면, 시작점(s)에서부터의 DAG 최단 경로를 찾을 수 있습니다.
Running Time
- 코드의 1번 줄의 Topological Sort에서 O(V+E)가 소요되고,
- 2번 줄의 Initialization에서 O(V)가 소요됩니다.
- 3번 줄 for 문에서 O(E)가 소요됩니다.
즉, DAG의 Shortest Path를 찾는 알고리즘의 수행시간은 여느 그래프 알고리즘과 마찬가지로 O(V+E)를 갖습니다.
참고 자료
https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
Introduction to Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare
This course is an introduction to mathematical modeling of computational problems, as well as common algorithms, algorithmic paradigms, and data structures used to solve these problems. It emphasizes the relationship between algorithms and programming and
ocw.mit.edu
'컴퓨터 과학(Computer Science) > 알고리즘(Algorithm)' 카테고리의 다른 글
| [알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) (0) | 2023.12.01 |
|---|---|
| [알고리즘] 위상 정렬(Topological Sort) (0) | 2023.12.01 |
| [알고리즘] 깊이 우선 탐색(DFS) - Python (0) | 2023.11.10 |
| [알고리즘] 너비 우선 탐색(BFS) - Python (0) | 2023.11.10 |
| [알고리즘] 퀵 정렬 (Quick Sort) - Python (0) | 2023.10.28 |
