Bellman-Ford (벨만-포드)

V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점(S)에서부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘이다. 

 

👀 특징 

• 음의 가중치를 갖는 간선도 존재 가능하다.
• 음의 사이클의 존재 여부를 확인할 수 있다.
• 최단거리를 구하기 위해서는 V-1번 E개의 모든 간선을 확인한다.
• 음의 사이클 존재 여부를 확인하기 위해 한 번 더 E개의 간선을 확인한다.
• 총 연산 횟수 = VxE
• ⌛️ 시간 복잡도 = O(VE)
• V번째 모든 간선을 확인했을 때 거리배열이 갱신되었다면 그래프 G는 음의 사이클을 가지는 그래프이다.

---

 

위와 같이 음의 가중치를 갖고 있는 그래프가 있을 때,

다익스트라로 정점 1에서 모든 정점까지의 거리를 구현한다면

1 ➔ 2 = 1

1 ➔ 2 ➔ 3 = 2

1 ➔ 2 ➔ 3 ➔ 4 = 4가 된다. (정점 2를 이미 방문했기 때문에 4 ➔ 2의 경로는 고려 X)

 

하지만 사실상 1 ➔ 2의 최단경로는 -∞ 이다. (음의 사이클이 존재하고 음수값이 더 크므로)

 

이러한 모순을 해결하기 위해 벨만포드 알고리즘을 사용해야 한다.

 

🕹️ 벨만 포드 과정

1️⃣ 출발지로부터 최단거리를 기록하는 배열(dist[])에 출발지는 0, 나머지는 INF(무한)으로 초기화한다.

2️⃣ 다음 과정을 V-1번 반복한다. 

1. 전체 간선 E개를 하나씩 방문해서 확인한다. (현재 정점의 모든 인접한 정점 탐색)
2. 기존에 저장된 인접 정점까지의 거리보다 현재 정점을 거치고 인접 정점에 도달하는 것이 더 짧을 경우 값을 갱신한다. 

3️⃣ 마지막으로 한 번 더(V번째) 2️⃣번의 과정을 반복하는데, 이 때 최단 거리 배열이 갱신된다면 음의 사이클이 존재하는 것이다. 

 

➡️ "동일 정점을 방문하지 않는다" 라는 제약조건 확인 ! (제약 조건이 없다면 음의 사이클 나올 수 있음)

 

 

👩‍💻 벨만 포드 코드 구현 

public class Main{

	static ArrayList<Info> graph;
    static final int INF = 1000000000;
    
    public static class Info{
    	int v, w, cost;
        
        public Info(int v, int w, int cost){
        	this.v = v;
            this.w = w;
            this.cost = cost;
        }
    }
    
    public static boolean BellmanFord(int n, int m, int start){
    	int[] dist = new int[n+1];
        Arrays.fill(dist, INF);
        dist[start]=0;
        
        for(int i=0; i<n; i++){
        	for(int j=0; j<m; j++){
            	Info info = graph.get(j);
                
                // 현재 간선에 들어오는 정점에 대해 비교
                if(dist[info.v]!=INF && dist[info.w] >= dist[info.v] + info.cost){
                	dist[info.w] = dist[info.v] + info.cost;
                }
            }
        }
        
        // 음수 가중치 확인
        for(int i=0; i<m; i++){
        	Info info = graph.get(i);
            
            if(dist[info.v]!=INF && dist[info.w] > dist[info.v] + info.cost){
            	System.out.println("음수 사이클 존재");
				return false;
            }
        }
     
        //출력
		for (int i = 1; i < dist.length; i++) {
			if (dist[i] == INF)
				System.out.print("INF ");
			else
				System.out.print(dist[i] + " ");
		}
		return true;
    }
    
    public static void main(String[] args) throws Exception{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine()); // 정점 개수
        int m = Integer.parseInt(br.readLine()); // 간선 개수
        
        graph = new ArrayList<>();
        
        for(int i=0; i<m; i++){
        	st = new StringTokenizer(br.readLine());
            
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            
            graph.add(new Info(v, w, cost));
        }
        
        BellmanFord(n, m, 4);
    }
}

 

 

💡 다익스트라와 벨만 포드 비교 

 

📍 다익스트라 

• 음의 가중치를 가질 수 없다.
• 벨만 포드 알고리즘보다 시간복잡도가 빠르다. ➡️ 가중치가 모두 양수라면 벨만 포드 사용 X

 

📍 벨만 포드 

• 음의 가중치를 가질 수 있다.
• 음의 사이클 존재여부를 확인한다. (존재 시 의미 없는 값 반환) 

 

 

 

참고자료

https://8iggy.tistory.com/153

https://www.youtube.com/watch?v=061eXyAFRuI