[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm) - JAVA / 자바

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

  : 음수인 가중치가 포함되어 있는 그래프에서 최단 거리를 구하는 알고리즘

 

음수 간선이 존재하지 않는다면 [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) - JAVA / 자바를 사용하여 문제를 해결하는 것이 실행 시간이 더 빠르다.

특징

  ① 음수인 사이클을 찾을 수 있다

  ② 매번 모든 간선을 확인하기에 연산 시간이 느리다

---

알고리즘

① 출발 노드 설정
② 최단 거리를 저장할 배열을 초기화
③ 전체 간선을 하나씩 확인
④ 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
⑤ 모든 노드에 연결되어 있는 모든 간선을 확인할 때까지 ③ ~ ④반복수행
  ⑤-1 이때, 마지막 반복에서 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재
         (∵ 음수 간선 순환은 돌면 돌수록 값이 작아지기 때문)

---

의사 코드 (Pseudo Code)

BellmanFord(G, sV, n)
	for(i ← 0; i<n; i ← i+1) do {
		distance[i] = Integer.MAX_VALUE;
	}
	distance[sV] ← 0;
	for(i ← 0; i<n; i ← i+1) do {
		for(j ← 0; j<n; j ← j+1) do {
			if(G[i][j] not Integer.MAX_VALUE) do {
				distance[j] = min(distance[j], distance[i]+G[i][j]);
				if(i == n) do {
                	return true;
				}
			}
		}
	}
    return false;
end BellmanFord()

---

Java 코드 구현

public static boolean bellman_ford(int num, int graph[][], int sV) {
	int distance[] = new int[num];
	Arrays.fill(distance, Integer.MAX_VALUE);
	distance[sV] = 0;
	for(int i=1; i<=num; i++)
		for(int j=1; j<=num; j++)
			if(graph[i][j] != Integer.MAX_VALUE) {
				distance[j] = Math.min(distance[j], distance[i]+graph[i][j]);
				if(i == num)
					return true;
			}
	return false;
}

시간 복잡도 (Time Complexity) = O(V x E)