벨만-포드 알고리즘(Bellman-Ford Algorithm)

이번에 배워볼 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)이다. 이 알고리즘 또한 이전에 배운 다익스트라 알고리즘처럼 그래프에서 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다.

벨만 포드 알고리즘은 다익스트라 알고리즘보다 시간이 더 걸리지만 음의 간선이 존재해도 최단 경로를 찾을 수 있는 알고리즘이다.

벨만 포드 알고리즘은 다이나믹 프로그래밍이라고 할 수 있다. 그 이유는 매번 저장해놓은 최소 비용을 이용해서 새로운 최소 비용으로 갱신하기 때문이다.

​벨만 포드 알고리즘이 다익스트라 알고리즘보다 시간이 오래 걸리는 이유는 다익스트라는 최소 비용을 가지는 간선만 우선적으로 뽑으면서 경우의 수를 줄여가며 비용을 갱신하였다. 하지만 벨만 포드 알고리즘은 음의 간선 때문에 모든 경우의 수를 다 탐색하는 알고리즘이다.

​

벨만 포드 알고리즘의 동작 원리는 다음과 같다.​

• 시작 정점을 선택한다.
• 모든 간선들을 탐색하면서, 시작 정점에서 다른 정점까지의 거리가 INF가 아니라면 거리를 갱신한다. 이 과정을 정점의 수-1번만큼 진행한다.
• 마지막으로 2번을 수행한다.

 

2번 과정에서 (정점의 수-1)번 만큼 진행하는 이유는 V개의 정점과 E개의 간선이 있는 가중 그래프에서 정점 A에서 정점 B까지의 최단 거리는 최대 V-1개의 정점을 지나기 때문이다.

V-1개 이상의 정점을 방문하는 것은 결국 중복 방문을 하는 것이기 때문에 최단 경로가 성립될 수 없다.

또한, 3번 과정에서 마지막으로 2번 과정을 한 번 더 수행하는 이유는 음의 사이클 유무를 판단하기 위해서이다. 만약 V 개의 정점을 지났는데 최단 경로가 갱신이 된다면 음의 사이클이 발생한 것이며 비용이 무한하게 갱신이 되기 때문에 최단 경로를 구할 수 없다.

​

벨만 포드 알고리즘의 동작 과정을 그림으로 이해해 보자.

 

가중치를 가지는 방향 그래프가 위 그림처럼 존재한다고 하자. 시작 정점을 1번으로 선택하고 남은 정점까지의 최단 경로를 구하는 과정을 살펴보자.

1번 정점에서 다른 정점으로 가는 비용은 1차원 배열로 표현한다. 초기 상태는 자신에게 가는 비용을 제외하고는 갈 수 없다는 의미로 INF로 표현한다.

 

첫 번째로 모든 간선을 통해 최단 경로를 갱신한다. 2번 정점으로 가는 비용은 1-4-2로 가능 비용 6으로 갱신되고, 3번 정점으로 가는 비용은 1-4-5-3으로 가는 비용 -1로 갱신된다.

4번 정점으로 가는 비용은 1-4로 가는 비용 3으로 갱신되고 5번으로 가는 비용은 1-4-5로 가는 비용 -3으로 갱신된다.

 

두 번째로 모든 간선을 통해 최단 경로를 갱신한다. 현재 2번으로 가는 비용 6보다 현재 3번으로 가는 비용(-1) + 4, 2번으로 가는 비용(6) = 5가 저렴하기 때문에 갱신해준다.

현재 3번으로 가는 비용 -1보다 현재 3번으로 가는 비용(-1) + 4, 5, 3번으로 가는 비용(-1) = -2가 저렴하기 때문에 갱신해 준다.

자세히 보면 3-4-5-3번 구간이 -1 값이 누적되는 음의 사이클이란 것을 확인할 수 있다. 음의 사이클로 인해 현재 3번으로 가는 비용이 -2로 갱신되면서 자연스럽게 4번과 5번으로 가는 비용이 -1만큼 갱신된다.

 

세 번째로 모든 간선을 통해 최단 경로를 갱신한다. 3-4-5-3의 음의 사이클 구간 때문에 3에서 갈 수 있는 2, 3, 4, 5번 정점으로 가는 비용이 -1만큼 갱신된다.

 

네 번째로 모든 간선을 통해 최단 경로를 갱신한다. 역시 마찬가지로 3-4-5-3의 음의 사이클 구간 때문에 3에서 갈 수 있는 2, 3, 4, 5번 정점으로 가는 비용이 -1만큼 갱신된다.

 

우리는 직접 그려보면서 음의 사이클의 유무를 확인하였지만 컴퓨터의 입장에서는 음의 사이클의 유무를 판단할 수가 없다.

따라서 마지막으로 모든 간선을 통해 경로를 갱신하며 음의 사이클이 발생하는지 확인한다. 3-4-5-3으로 -1이 누적되는 음의 사이클 구간이 존재하기 때문에 2, 3, 4, 5번 정점들의 비용이 -1만큼 감소하면서 갱신이 되는 것을 확인할 수 있다.

즉, 음의 사이클이 존재하기 때문에 모든 정점에 대해 최단 경로를 구할 수 없다.

 

벨만 포드 알고리즘은 정점의 수만큼 모든 간선을 탐색하기 때문에 O(VE)​의 시간 복잡도를 가진다.

​

벨만 포드 알고리즘을 Java로 구현한 코드는 다음과 같다.

import java.util.ArrayList;
import java.util.Arrays;

class MyGraph {
	final int INF = 987654321;
	int N;
	int[] dist;
	ArrayList<Edge> edgeList;
	
 	class Edge {
		int from, to, cost;
		
		public Edge(int from, int to, int cost) {
			this.from = from;
			this.to = to;
			this.cost = cost;
		}
	}
	
	public MyGraph(int N) {
		this.N = N;
		edgeList = new ArrayList<>();
	}

	public void make_directedEdge(int from, int to, int cost) {
		edgeList.add(new Edge(from, to, cost));
	}

	public void bellman_Ford(int v) {
		// 최소 비용 초기화
		dist = new int[N+1];
		Arrays.fill(dist, INF);
		dist[v] = 0;
		
		// 정점의 수만큼 반복
		for (int i = 1; i <= N; ++i) {
			// 모든 간선을 돌면서
			for (int j = 0; j < edgeList.size(); ++j) {
				int from = edgeList.get(j).from;
				int to = edgeList.get(j).to;
				int cost = edgeList.get(j).cost;
				
				// from까지 갈수 없다면 갱신 x 
				if (dist[from] == INF) continue;
				
				// to까지 가는 비용보다 from까지 가는 비용 + from에서 to까지 가는 비용이 더 저렴하다면 갱신
				if (dist[to] > dist[from] + cost) {
					// v번째 횟수에 갱신이 된다면 음의 사이클이 존재하기 때문에 최단 경로를 구할 수 없음.
					if (i == N) {
						System.out.println("음의 사이클 존재");
						return;
					}
					dist[to] = dist[from] + cost;
				}
			}
		}
		
		for (int i = 1; i <= N; ++i) {
			System.out.print(dist[i]==987654321?"INF ":dist[i]+" ");
		}
	}
}

public class Blog {

	public static void main(String[] args) {
		MyGraph mg = new MyGraph(5);
		mg.make_directedEdge(1, 2, 7);
		mg.make_directedEdge(1, 3, 5);
		mg.make_directedEdge(1, 4, 3);
		mg.make_directedEdge(3, 4, 3);
		mg.make_directedEdge(3, 5, 3);
		mg.make_directedEdge(4, 2, 3);
		mg.make_directedEdge(4, 5, -6);
		mg.make_directedEdge(5, 3, 2);
		mg.bellman_Ford(1);
	}
}