안녕하세요 이번 시간에는 벨만-포드 알고리즘에 대해 알아보는 시간을 갖도록 하겠습니다.
벨만-포드 알고리즘이란 그래프에서 최단 거리를 구하는 알고리즘으로 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색하는 알고리즘입니다. 다익스트라 알고리즘과 유사한 특징을 띠나 다익스트라와 달리 음수 가중치가 존재하여도 수행 가능하다는 차이점이 있습니다. 이를 이용하여 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있습니다. 단 시간복잡도는 O(노드 수 X 간선 수)로 다익스트라보다는 느린 처리 시간을 가집니다. 실제 코딩 테스트에서는 최단 거리를 구하는 문제보다 음수 사이클을 판별하는 문제가 더 빈번하게 출제된다고 합니다.
벨만-포드 알고리즘의 동작 방식은 다음과 같습니다.
1. 간선 클래스 생성 : 시작점, 도착점, 가중치를 가지는 간선 클래스를 생성합니다.
2. 간선 리스트(일차원 배열)로 그래프 구현하고 최단 경로 배열 초기화
- 여기서 주의할 점은 간선 리스트의 크기는 간선의 개수만큼 설정해야 합니다.
- 노드의 개수만큼 반복하여 각 반복 루프 내에서 모든 간선을 확인하여 정답 배열 업데이트
- 각 간선의 시작점의 최단 경로 배열값이 최댓값이 아닌 경우 시작점에서 가중치를 더한 값과 끝값의 최솟값을 추가합니다 (distance[edge.end] = Math.min(distance[edge.end], distance[edge.start] + edge.time);)
- 음수 사이클 유무 확인
- 각 간선의 시작점의 최단 거리 배열값이 최댓값이 아니고 끝값의 최단 거리 배열이 시작값의 최단 거리 배열에 가중치 더한 것보다 클 경우 음수 사이클이 존재합니다.
백준 11675(타임머신) 문제를 통해 벨만-포드 알고리즘을 구현해보겠습니다. N개의 도시가 있을 때 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 문제입니다. 간선의 가중치가 양수가 아닌 경우가 존재하기 때무네 벨만-포드 알고리즘을 선택합니다. 여기서 간선 리스트의 크기는 간선의 개수인 M+1만큼 설정합니다.
import java.util.*;
import java.io.*;
class Main{
static int N,M;
static Edge[] edges;
static long[] distance;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
distance = new long[N+1];
Arrays.fill(distance,Integer.MAX_VALUE);
distance[1] = 0;
edges = new Edge[M+1];
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 t = Integer.parseInt(st.nextToken());
edges[i] = new Edge(a,b,t);
}
for(int i=1;i<N;i++){
for(int j=0;j<M;j++){
Edge edge = edges[j];
// if(
// distance[edge.start] != Integer.MAX_VALUE &&
// distance[edge.end] > distance[edge.start] + edge.time
// ){
// distance[edge.end] = distance[edge.start] + edge.time;
// }
if(distance[edge.start] != Integer.MAX_VALUE){
distance[edge.end] = Math.min(distance[edge.end], distance[edge.start] + edge.time);
}
}
}
boolean minusCycle = false;
for(int i=0;i<M;i++){
Edge edge = edges[i];
if(
distance[edge.start] != Integer.MAX_VALUE &&
distance[edge.end] > distance[edge.start] + edge.time
){
minusCycle = true;
}
}
if(!minusCycle){
for(int i=2;i<=N;i++){
if(distance[i] == Integer.MAX_VALUE) System.out.println(-1);
else System.out.println(distance[i]);
}
}
else System.out.println(-1);
}
static class Edge{
int start;
int end;
int time;
Edge(int start, int end, int time){
this.start = start;
this.end = end;
this.time = time;
}
}
}벨만-포드 알고리즘의 유형은 음수 또는 양수 사이클이 존재하는지 파악해야 하는 경우에서 자주 사용됩니다.
백준 1219(오민식의 고민) 문제의 경우 N개의 도시 중 출발 도시에서 도착 도시에 도착할 때 가지고 있는 돈의 액수를 최대로 하려고 하는 프로그램을 작성하는 문제입니다. 음의 값이 존재할 수 있기 때문에 벨만-포드 알고리즘을 사용합니다. 하지만 벨만-포드의 경우 최솟값을 구하는 문제인 반면 이 문제를 최댓값을 구해야 하기 때문에 양의 사이클 여부를 체크해야 합니다. 최단 경로 배열을 충분히 작은 값으로 초기화한 후 벨만-포드 알고리즘을 진행합니다. 이 때 반복 횟수를 N보다 적당히 크게 진행한 후 N회 이상 반복했을 경우 최단 경로 배열값을 충분히 큰 값으로 변경합니다. 최단 경로 배열값이 충분히 큰 값일 경우 무한히 돈을 벌 수 있는 사이클에 들어온 것이므로 반복문 내에서 계속 충분히 큰 값을 출력합니다.
