단일 출발지 최단 경로 Single Source Shortest Path
Single Source Shortest Path란, 말 그대로 하나의 출발지(Single Source)에서 시작한 최단 경로(Shortest Path)를 말합니다.
벨만-포드 알고리즘 Bellman-Ford Algorithm
Bellman-Ford 알고리즘은, Dijkstra 알고리즘과 함께 가중치가 있고(Weighted) 방향이 있는(Directed) 그래프에서 Single Source Shortest Path(SSSP)을 구하는 알고리즘입니다. 가중치(Weight)가 0보다 크거나 같은 그래프만 풀 수 있는 Dijkstra 알고리즘과는 다르게, Bellman-Ford 알고리즘은 Negative Weighted Edge가 존재하는 경우에도 SSSP 문제를 풀 수 있습니다.
Bellman-Ford 알고리즘은 두가지의 주요 기능을 가지고 있습니다.
- Shortest Path (with Negative edge)를 찾는다.
- Negative Cylcle을 감지한다.
여기서 Negative Cycle이란, 다음 그림과 같이 어떠한 한 순환(cycle)을 순환하면 순환할수록 점점 음수값이 커져 결국 -∞로 발산하는 불필요한 순환을 말합니다. Bellman-Ford 알고리즘은 이러한 Negative Cycle을 감지하는 기능을 가집니다.
참고로 Bellman-Ford 알고리즘에는 Relaxation 개념이 사용됩니다. 아래는 Relaxation에 대한 설명이 포함된 글입니다.
[알고리즘] DAG 최단 경로 문제(DAG Shortest Path Problem)
Directed Acyclic Graph(DAG) DAG란 그래프 연결에 방향이 있고(Directed), 한 곳에서 순환이 발생하지 않는(Acyclic) 그래프(Graph)를 의미합니다. Edge Relaxation DAG Shortest Path 문제를 풀기 위해 Edge Relaxation 개념이
stevenkim1217.tistory.com
Bellman-Ford 알고리즘 Pseudo Code
Bellman-Ford 알고리즘의 Pseudo Code는 다음과 같습니다.
- 위 코드의 오른쪽에 표시되어 있는 것 처럼 윗 부분의 for문은 Shortest Path를 찾기 위해 Relaxation을 수행하는 부분이고,
- 아래의 for문은 Negative Cycle이 존재하는지 판별하는 부분입니다.
Bellman-Ford 알고리즘의 원리
위 Pseudo Code를 이용하여 Bellman-Ford 알고리즘의 원리에 대해 알아보겠습니다. 아래 그래프에 Bellman-Ford 알고리즘을 적용하겠습니다.
1. Shortest Path 찾는 과정
- 우선 시작하고자 하는 노드(s)만을 0으로 초기화하고, 나머지 노드는 모두 무한대로 초기화합니다. 노드의 값을 무한대로 초기화 하는 이유는, 이후 취할 relaxation이 비교 후 작은 수로 업데이트 해주는 특성을 가지고 있기 때문입니다.
- 그래프의 어느 vertex든지 시작 지점으로 선택할 수 있지만, 본 내용에서는 위와 같은 순서로 순회하는 예시를 보이겠습니다. 순서는 임의로 지정된 것으로 얼마든지 바뀔 수 있습니다.
- 현재 위 edge의 나열을 보면, t → x → y → z → s 노드의 순서로 진행됨을 얼추 알 수 있습니다.
- 먼저 t 노드의 인접 vertices에 대해 Relax를 진행합니다. 하지만, t의 값이 무한대이므로, relax 이후의 값이 그대로입니다.
- 그 다음으로 x 노드에 대해 인접 노드에 대한 Relax를 진행합니다. 하지만 t와 마찬가지로 현재 x의 값이 무한대이기 때문에 relaxation 이후에도 그래프의 값의 변화가 없습니다.
- y 노드와 z 노드에 대해서도 Relax를 수행합니다. 마찬가지로 모두 무한대의 값을 가지므로 변화가 없습니다.
- 하지만 그 다음 차례인 s 노드에 대해서는 Relaxation을 수행했을 때, 0+6<∞ 이고 0+7<∞ 이므로 t와 y노드의 값이 업데이트 됩니다.
- (a) ~ (j)까지 해당 edge 순서를 모두 돌았으므로, 다시 (t,x)부터 relaxation을 수행합니다.
- 이 다음번 trial 부터는 노드에 무한대의 값이 점점 사라져 가게 되므로, 눈에 띄게 Relax가 수행됩니다.
위와 같은 방식으로 "모든 edge에 대해 Relaxation을 취할 때까지" 즉, "모든 edge에 대해 (Vertex 개수)-1번의 Relaxation을 취할 때까지" 이 과정을 반복합니다. 이에 대한 그림은 아래와 같습니다.
2. Negatice Cycle 감지하는 과정
이번에는 Negatice Cycle을 감지하는 과정입니다. 위와 같은 방식으로 그래프를 순회하면서, v.d > u.d + w(y,v)가 한 번 더 발생하는지의 여부를 감지합니다.
아래는 이전 게시물에서 설명한 Edge Relaxation의 과정에 대한 설명입니다.
Edge relaxation은 만약 v.d > u.d + w(y,v)가 존재한다면 더 작은 쪽으로 업데이트합니다.
그런데 다음 Bellman-Ford 코드에서 위 for loop을 돌며 Relaxation 작업이 모두 끝났음에도 불구하고, 만약 Relaxation이 될 만한 여지가 한 번 더 감지된다면,
그것은 Negative Cylce이 그래프 내에 존재한다는 의미입니다.
Running Time
Bellman-Ford 알고리즘의 Running Time은 O(VE) + O(V) + O(E) 즉, O(VE)입니다.
다음은 Negative Edge가 없는 그래프에서 SSSP 문제를 푸는 알고리즘인 Dijkstra 알고리즘에 대한 게시물입니다.
[알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm)
단일 출발지 최단 경로 Single Source Shortest Path Single Source Shortest Path란, 말 그대로 하나의 출발지(Single Source)에서 시작한 최단 경로(Shortest Path)를 말합니다. 다익스트라 알고리즘 Dijkstra Algorithm Dijkst
stevenkim1217.tistory.com
참고 자료
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
https://ocw.snu.ac.kr/node/32373
Introduction to Algorithms | SNU OPEN COURSEWARE
ocw.snu.ac.kr
'컴퓨터 과학(Computer Science) > 알고리즘(Algorithm)' 카테고리의 다른 글
| [알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) (0) | 2023.12.01 |
|---|---|
| [알고리즘] 위상 정렬(Topological Sort) (0) | 2023.12.01 |
| [알고리즘] DAG 최단 경로 문제(DAG Shortest Path Problem) (0) | 2023.12.01 |
| [알고리즘] 깊이 우선 탐색(DFS) - Python (0) | 2023.11.10 |
| [알고리즘] 너비 우선 탐색(BFS) - Python (0) | 2023.11.10 |
