[알고리즘] 최단 경로 알고리즘 : 벨만 포드 (Bellman-Ford)

벨만 포드 (Bellman-Ford)

• 단일 시작점 최단 경로 알고리즘
• 음수 간선 포함 가능

동작 과정

그래프에서 최단 경로가 한 정점을 두 번 지나는 일은 없다.

최단 경로는 최대 V개의 정점을 갖기 때문에 잘해야 V-1개의 간선을 가질 수 있다.

따라서 모든 간선에 대한 완화 과정은 V-1번이면 충분하다.

 

음수 사이클 판정

완화를 V번 시도하면 된다.

음수 사이클이 존재하지 않다면 V-1번이면 최단 거리를 찾아낼 수 있다.

만일 V번째 완화 과정에서 한번더 완화가 성공한다면 이는 음수 사이클이 존재한다고 생각할 수 있게 된다.

static int n; // 정점의 개수 
static int m; // 간선의 개수 
static ArrayList<path>[] al = new ArrayList[n+1]; // 그래프의 (연결 정점 번호, 간선 가중치)쌍을 담는다. 
static int distance[] = new int[n+1]; // 그래프의 거리를 담는 변수 

Arrays.fill(distance, Integer.MAX_VALUE); 
for(int i = 0; i < n+1; i++) { 
	al[i] = new ArrayList<>(); 
}

// 간선 입력 (a, b, c): a -> b 로 가는 가중치 c을 가지는 간선 
for(int i = 0; i < m; i++) { 
	StringTokenizer st = new StringTokenizer(br.readLine()); 
    int a = Integer.parseInt(st.nextToken()); 
    int b = Integer.parseInt(st.nextToken()); 
    int c = Integer.parseInt(st.nextToken()); 
    al[a].add(new path(b, c));
}

static boolean bellmanFord() {
	dis[1] = 0; // 출발 노드 초기화
    
    for(int i = 1; i < n; i++) { // n-1번 완화 과정
		for(int j = 1; j < road.length; j++) { 
			for(edge next: road[j]) { 
				if(dis[j] + next.time < dis[next.node]) { 
					dis[next.node] = dis[j] + next.time; 
				} 
			}	 
		} 
	} 
	
    for(int j = 1; j < road.length; j++) { // n번째 완화 과정
		for(edge next: road[j]) { 
			if(dis[j] + next.time < dis[next.node]) { // 음수 사이클 존재하는 경우
				return true; 
			} 
		} 
	} 
	return false; // 음수 사이클 존재하지 않는 경우
} 

static class edge{
	int node; // 노드 
	int time; // 걸리는 시간
	
    edge(int node, int time) { 
		this.node = node; 
		this.time = time; }
}