벨만포드 알고리즘
🔑그래프에서 최단거리를 구하는 알고리즘
✏️음수 가중치 에지가 있어도 수행이 가능하며, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
시간 복잡도: O(VE)
1. 에지 리스트로 그래프 구현> 최단 경로 배열 초기화
tip) 자바의 경우, Arrays.fill을 사용하면 빠르다.
static final int INF = Integer.MAX_VALUE;
Arrays.fill(arr, INF);
2. 모든 에지를 확인하면서 정답 배열을 업데이트 해준다.
노드 개수가 N이라고 가정할 때, 최단거리 배열에서 업데이트 반복 횟수는 N-1번이다.
N개의 노드가 있고 음수 사이클이 없을 때 최단 경로를 구성하는 엣지의 개수는 최대 N-1개가 된다. (N개가 될 수가 없다)
✏️업데이트 조건
Distance[start]!=INF && Distance[end]>Distance[start]+weight이면
Distance[end]=Distance[start]+weight
3. 음수 사이클 확인
모든 에지를 한번씩 다시 확인하여 업데이트 되는 노드가 발생하는지 확인해야 함.
업데이트 되는 노드가 있는 경우: 음수 사이클 O
음수 사이클이 존재하는 경우, 이 사이클을 무한하게 돌수록 가중치가 계속 감소하므로 최단거리를 구할 수 없다.
음수 사이클이 존재하지 않는다면 계속해서 탐색해도 최단거리 배열의 값은 업데이트 되지 않을 것이다.
처음에는 음수 사이클을 이해하기 어려웠는데, 아래 문제를 통해서 확실히 정리하고 넘어가면 좋을 것 같다.
백준 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
벨만포드 알고리즘 부분
//N: 노드갯수 M:엣지 갯수
for(int i = 1; i < N; i++) { //N-1만큼 반복
for(int j = 1; j <= M; j++) {
Edge ed = edge[j];
//업데이트 조건
if(dist[ed.s] != INF
&& dist[ed.s]+ed.t <dist[ed.e]) {
dist[ed.e] = dist[ed.s]+ed.t;
}
}
}
벨만포드 알고리즘을 수행하는 코드를 살펴보면,
j의 범위를 1~M까지로 설정하여 이중for문을 돌리면서 모든 Edge들, 즉 edge[1~M]을 N-1번만큼 탐색하고 있다.
//벨만포드 쭉 돌리고 한번 더 돌렸을 때 만약 값이 또 바뀐다면 음수가 존재한다는 뜻.
boolean isCycle = false;
for(int i = 1; i <= M; i++) {
Edge ed = edge[i];
if(dist[ed.s] != INF
&& dist[ed.s]+ed.t < dist[ed.e]) {
isCycle = true; //true로 바꿔준다.
}
}
이후에 한번 더 모든 edge를 탐색하면서 값이 업데이트되는지 확인하는 작업을 해준다.
벨만포드 알고리즘은 노드가 아니라 edge를 중심으로 생각하면 이해가 더 쉬운 것 같다.
전체코드
package baekjoon;
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static long dist[];
static Edge edge[];
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //도시의 개수
M = Integer.parseInt(st.nextToken()); //버스노선의 개수
//초기화
dist = new long[N+1];
edge = new Edge[M+1];
Arrays.fill(dist, INF);
for(int i = 1; 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());
edge[i] = new Edge(a,b,c);
}
//벨만포드
dist[1] = 0; //출발도시는 1
for(int i = 1; i < N; i++) { //N-1만큼 반복
for(int j = 1; j <= M; j++) {
Edge ed = edge[j];
if(dist[ed.s] != INF
&& dist[ed.s]+ed.t <dist[ed.e]) {
dist[ed.e] = dist[ed.s]+ed.t;
}
}
}
//벨만포드 쭉 돌리고 한번 더 돌렸을 때 만약 값이 또 바뀐다면 음수가 존재한다는 뜻.
boolean isCycle = false;
for(int i = 1; i <= M; i++) {
Edge ed = edge[i];
if(dist[ed.s] != INF
&& dist[ed.s]+ed.t < dist[ed.e]) {
isCycle = true; //true로 바꿔준다.
}
}
if(!isCycle) {
//2부터
for(int i = 2; i <= N;i++) {
if(dist[i] == INF) bw.write("-1"+"\n");
else bw.write(Long.toString(dist[i])+"\n");
}
}
else bw.write("-1"+"\n");
bw.newLine();
br.close();
bw.close();
}
}
class Edge{
int s, e, t; //start, end ,time
public Edge(int s, int e, int t) {
this.s = s;
this.e = e;
this.t = t;
}
}
백준 1865 웜홀
1865번: 웜홀
첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500),
www.acmicpc.net
해당 문제는 단 도로는 방향이 없으며 웜홀은 방향이 있다. 라는 조건때문에 도로의 경우 양방향이 가능하다. 따라서 ArrayList를 사용했다. 문제를 잘 읽는 습관을 들이자.
import java.io.*;
import java.util.*;
public class Main {
static int TC, N, M, W;
static long dist[];
static ArrayList<ArrayList<Edge>> a;
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
TC = Integer.parseInt(br.readLine());
for (int tc = 0; tc < TC; tc++) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 지점의 개수
M = Integer.parseInt(st.nextToken()); // 도로의 개수
W = Integer.parseInt(st.nextToken()); // 웜홀의 개수
dist = new long[N + 1];
a = new ArrayList<>();
for (int i = 0; i <= N; i++) {
a.add(new ArrayList<>());
}
Arrays.fill(dist, INF);
for (int i = 0; i < M + W; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
if (i < M) {
a.get(s).add(new Edge(e, t));
a.get(e).add(new Edge(s, t));
} else {
a.get(s).add(new Edge(e, -t));
}
}
if (!bellmanFord()) bw.write("NO");
else bw.write("YES");
bw.newLine();
}
br.close();
bw.flush();
bw.close();
}
static boolean bellmanFord() {
dist[1] = 0;
for (int i = 1; i < N; i++) {
for (int j = 1; j <= N; j++) {
for (Edge e : a.get(j)) {
if (dist[j] + e.t < dist[e.e]) {
dist[e.e] = dist[j] + e.t;
}
}
}
}
// 음수 사이클
for (int j = 1; j <= N; j++) {
for (Edge e : a.get(j)) {
if (dist[j] + e.t < dist[e.e]) {
return true;
}
}
}
return false;
}
}
class Edge {
int e, t; // end, time
public Edge(int e, int t) {
this.e = e;
this.t = t;
}
}
🪄벨만포드 음수사이클 판단 더 빠른 방법
static boolean bellmanFord() {
dist[1] = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (Edge e : a.get(j)) {
if (dist[j] + e.t < dist[e.e]) {
dist[e.e] = dist[j] + e.t;
if( i == N ) return true;
}
}
}
}
return false;
}
'Algorithms > study log' 카테고리의 다른 글
[java] 큐 / 우선순위 큐 / 힙 (0) | 2024.02.23 |
---|---|
[java] 플로이드-워셜 알고리즘 (0) | 2024.02.06 |
[java] 다익스트라 알고리즘 (0) | 2024.02.01 |
[백준 나무자르기] 이분탐색시 시작 혹은 끝 지점 설정하는 방법 (0) | 2024.01.17 |
[java] 이분탐색 (2) | 2024.01.12 |