[java] 벨만포드 알고리즘

벨만포드 알고리즘

🔑그래프에서 최단거리를 구하는 알고리즘
✏️음수 가중치 에지가 있어도 수행이 가능하며, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
시간 복잡도: 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: 노드갯수 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번: 웜홀

해당 문제는 단 도로는 방향이 없으며 웜홀은 방향이 있다. 라는 조건때문에 도로의 경우 양방향이 가능하다. 따라서 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;
    }