벨만-포드(bellman-ford moore) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘입니다.
| 기능 | 특징 | 시간 복잡도 (V: 노드 수, E: 에지 수) |
| 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 | - 음수 가중치 에지가 있어도 수행할 수 있음. - 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음. |
O(VE) |
벨만 - 포드의 핵심 이론
아래 3가지 단계로 동작합니다.
1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화.
벨만-포드 알고리즘은 에지를 중심으로 동작하여 에지 리스트로 구현합니다. 다익스트라와 똑같이 출발 노드는 0, 다른 노드들은 ∞ 로 초기화합니다.
아래 그래프의 예에서 출발 노드는 1로 하여 벨만-포드 알고리즘을 진행해보겠습니다.
2. 모든 에지를 확인해서 정답 배열을 업데이트
최단 거리 배열에서 업데이트 반복 횟수는 노드 개수 - 1 입니다. 노드 개수가 N 이고 음수 사이클이 없다면 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N - 1 개 이기 때문입니다.
오른쪽 그림처럼 N 이 4 일 때 음수 사이클이 없다면 1 에서 4로 가는 최단 거리를 최대 3개의 에지일 때까지 가능합니다. (음수 사이클이 없을 때 최대 에지 개수가 나오려면 편향 트리 형태에서 양 끝 노드를 선택해야 함.)
특정 에지 E = (s, e, w) 에서 아래 조건을 만족하면 업데이트를 실행합니다.
D[s] != ∞ && D[e] > D[s] + w 일 때 D[e] = D[s] + w 로 배열의 값을 업데이트
3. 음수 사이클 유무 확인
음수 사이클 유무를 확인하기 위해 모든 에지를 한 번씩 다시 사용해서 업데이트 되는 노드가 발생하는지 확인합니다.
만약 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻이 되고 2 단계에서 도출한 정답 배열이 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻이 됩니다.
음수 사이클이 존재하면 이 사이클을 무한하게 돌 수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없습니다.
실제 알고리즘 코딩 테스트에서는 벨만-포드 알고리즘을 사용해서 최단 거리를 구하는 문제보다 음수 사이클을 판별하는 문제가 더 빈번히 출제됩니다. 따라서 '3. 음수 사이클 유무 확인' 의 과정을 꼭 잊지 말고 확인해야 합니다.
백준 11657 타임머신
https://www.acmicpc.net/problem/11657
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
1. 문제 분석
시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제이지만 특이한 점은 에지(이동 시간)이 0과 음수도 가능하다는 것입니다. 에지가 음수가 될 수 있을 때는 벨만-포드 알고리즘을 사용하면 됩니다.
2. 손으로 풀기
1. 에지 리스트에 에지 데이터를 저장한 후 거리 배열을 초기화.
2. 아래 순서에 따라서 벨만-포드 알고리즘을 수행.
▶ 벨만-포드 알고리즘 수행 과정
a. 모든 에지와 관련된 정보를 가져온 후에 아래 조건에 따라 거리 배열(ans)의 값을 업데이트
▪️ 출발 노드가 방문한 적이 없는 노드(출발 노드 거리 == ∞) 일 때 값을 업데이트하지 않는다.
▪️ 출발 노드의 거리 배열값 + 에지 가중치 < 종료 노드의 거리 배열값 이면 종료 노드의 거리 배열값을 업데이트한다.
b. '노드 개수 - 1' 번만큼 a 을 반복한다.
c. 음수 사이클 유무를 알기 위해서 모든 에지에 관해 다시 한번 a 을 수행한다. 이 때 값이 업데이트되는 조건을 한번이라도 만족한다면 음수 사이클이 존재한다고 판단한다.
3. 음수 사이클이 존재하면 -1, 존재하지 않으면 거리 배열의 값을 출력. 단 거리 배열의 값이 ∞ 이라면 -1 을 출력.
3. 슈도코드
N: 노드 수 , M: 에지 수
graph: Edge[]
ans[N+1]: 정답 배열
for(M){ 에지 입력 받기 }
for(노드 개수 - 1 번 반복) {
모든 에지를 검사
ans[출발노드] != ∞ 이고 ans[도착] > ans[출발노드] + weight 이면
ans 을 업데이트
}
모든 에지를 검사
ans[출발노드] != ∞ 이고 ans[도착] > ans[출발노드] + weight 이면
ans 가 업데이트 되는 것이므로 음수 사이클이 존재하는 것임. -1 출력, 끝
아니면
ans[2] 부터 ans[N] 까지 출력4. 코드
public class BaekJun11657 {
static int N, M;
static Edge[] graph;
static long[] ans;
static boolean isMinusCycle = false;
public static void main(String[] args) throws IOException {
input();
bellmanFord();
isMinusCycle = checkMinusCycle();
output(isMinusCycle);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new Edge[M];
ans = new long[N + 1];
Arrays.fill(ans, Integer.MAX_VALUE);
ans[1] = 0;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
graph[i] = new Edge(A, B, C);
}
br.close();
}
private static void bellmanFord() {
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < M; j++) {
if (ans[graph[j].start] != Integer.MAX_VALUE &&
ans[graph[j].arrival] > ans[graph[j].start] + graph[j].weight) {
ans[graph[j].arrival] = ans[graph[j].start] + graph[j].weight;
}
}
}
}
private static boolean checkMinusCycle() {
for (int i = 0; i < M; i++) {
if (ans[graph[i].start] != Integer.MAX_VALUE &&
ans[graph[i].arrival] > ans[graph[i].start] + graph[i].weight) {
isMinusCycle = true;
break;
}
}
return isMinusCycle;
}
private static void output(boolean isMinusCycle) {
if (isMinusCycle) {
System.out.println("-1");
} else {
for (int i = 2; i <= N; i++) {
if (ans[i] == Integer.MAX_VALUE) {
System.out.println("-1");
} else {
System.out.println(ans[i]);
}
}
}
}
static class Edge {
int start;
int arrival;
int weight;
public Edge(int start, int arrival, int weight) {
this.start = start;
this.arrival = arrival;
this.weight = weight;
}
}
}
백준 1219 오민식의 고민
https://www.acmicpc.net/problem/1219
1219번: 오민식의 고민
첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착
www.acmicpc.net
1. 문제 분석
기존 벨만-포드 알고리즘은 최단 거리를 구하는 알고리즘이지만 이 문제에서는 도착 도시에 도착할 때 돈의 액수를 최대로 해야 하기 때문에 업데이트 방식을 반대로 변경해야 합니다.
돈을 무한히 버는 케이스는 양수 사이클이 있는 경우입니다. 그런데 예외 처리가 하나 필요합니다. 아래 그림처럼 양수 사이클이 있어도 출발 노드에서 양수 사이클을 통해서 도착 도시로 갈 수 없는 경우입니다.
이 부분을 해결할 수 있는 방법은 여러가지가 있습니다. 그 중 하나는 에지의 업데이트를 N-1 번이 아닌 충분히 큰 수(도시 개수 N 의 최대치 = 100) 만큼 추가로 돌리면서 업데이트를 수행하도록 로직을 변경하여 해결하겠습니다. 에지를 충분히 탐색하면서 양수 사이클에서 도달할 수 있는 모든 노드를 양수 사이클에 연결된 노드로 업데이트하기 위해서입니다.
2. 손으로 풀기
1. 에지 리스트에 에지 데이터를 저장하고, 거리 배열값을 초기화. 최초 시작점에 해당하는 거리 배열값은 0으로 초기화.
2. 아래 순서에 따라 변형된 벨만-포드 알고리즘 수행.
변형된 벨만-포드 알고리즘
①. 모든 에지와 관련된 정보를 가져와서 다음 조건에 따라 거리 배열의 값을 업데이트
① - a. 시작 도시가 방문한 적이 없는 도시일 때(출발 노드 = -∞) 업데이트를 하지 않음.
① - b. 시작 도시가 양수 사이클과 연결된 도시일 때(도착 노드 == ∞) 도착 도시도 양수 사이클과 연결된 도시로 업데이트.
① - c. '도착 도시값 < 시작 도시값 + 도착 도시 수입 - 에지 가중치' 일 때 더 많이 벌 수 있는 새로운 경로로 도착한 것임. 값을 업데이트.
②. 노드보다 충분히 많은 값(N+100) 으로 ① 을 반복. 이것을 Relaxation 을 해준다고 합니다.
위 그림에서는 5부터 양수 사이클이 전파되고 있습니다.
3. 도착 도시의 값에 따라 결과를 출력.
3. 슈도코드
N; 노드 수, S: 시작 도시, A: 도착 도시, M: 에지 개수
edges: 그래프 에지 배열
sales: 각 도시에서 버는 돈 배열
dist: 거리 배열 -> 시작 도시는 0 나머지는 -∞
result: 도착도시까지의 거리 저장 변수
그래프 에지 데이터 저장.
// 벨만 포드
for (N + 100 번 반복해서 Relaxation){
for(모든 에지에 대해서) {
출발 노드가 방문하지 않은 노드라면 (-∞ 라면) continue;
출발 노드가 양수 사이클에 연결된 노드라면 (∞ 라면)
종료 노드의 값을 ∞ 로 업데이트
종료 노드의 값 < 출발 노드의 값 + 도착 도시에서의 수입 - weight 이면
종료 노드의 값을 업데이트
만약 N-1 반복 이후에 업데이트가 되는 것이라면
이 종료 노드를 양수 사이클 연결 노드로 업데이트
}
}
// 도착 도시의 값에 따른 결과 출력
도착 도시가 -∞ -> 도착 불가 gg 출력
도착 도시가 ∞ -> 돈을 무한대로 벌 수 있음 Gee 출력
이외의 경우 -> 도착 도시의 값 출력
static class Edge{
int start, arrival, weight;
}4. 코드
public class BaekJun1219 {
static int N, S, A, M;
static Edge[] edges;
static long[] dist;
static long[] sales;
public static void main(String[] args) throws IOException {
input();
modifiedBellmanFord();
output();
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
A = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
edges = new Edge[M];
dist = new long[N];
sales = new long[N];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
edges[i] = new Edge(s, e, w);
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
sales[i] = Long.parseLong(st.nextToken());
dist[i] = Long.MIN_VALUE;
}
dist[S] = sales[S];
br.close();
}
private static void modifiedBellmanFord() {
for (int i = 0; i < N * 2; i++) {
for (int j = 0; j < M; j++) {
Edge curEdge = edges[j];
if (dist[curEdge.start] == Long.MIN_VALUE) {
continue;
} else if (dist[curEdge.start] == Long.MAX_VALUE) {
dist[curEdge.arrival] = Long.MAX_VALUE;
} else if (dist[curEdge.start] != Integer.MIN_VALUE &&
dist[curEdge.arrival] < dist[curEdge.start] - curEdge.weight + sales[curEdge.arrival]) {
dist[curEdge.arrival] = dist[curEdge.start] - curEdge.weight + sales[curEdge.arrival];
if (i > N - 1) {
dist[curEdge.arrival] = Long.MAX_VALUE;
}
}
}
}
}
private static void output() {
if (dist[A] == Long.MIN_VALUE) {
System.out.println("gg");
} else if (dist[A] == Long.MAX_VALUE) {
System.out.println("Gee");
} else {
System.out.println(dist[A]);
}
}
static class Edge {
int start;
int arrival;
int weight;
public Edge(int start, int arrival, int weight) {
this.start = start;
this.arrival = arrival;
this.weight = weight;
}
}
}
'Java > 코딩테스트' 카테고리의 다른 글
| [JAVA] 최소 신장 트리 알고리즘 자바 백준 BOJ 1197, 17472, 1414 (2) | 2023.08.24 |
|---|---|
| 플로이드-워셜 알고리즘 자바 백준 BOJ 11404, 11403 (1) | 2023.08.21 |
| 우선순위 큐를 이용한 다익스트라 알고리즘 자바 백준 BOJ 1735, 1916, 1854 (0) | 2023.08.17 |
| 위상정렬 자바 백준 BOJ 2252, 1516, 1948 (0) | 2023.08.07 |
| 유니온 파인드 자바 백준 BOJ 1717, 1976, 1043 (0) | 2023.08.05 |