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

벨만-포드 알고리즘이란?

---

 -> 그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용하는 알고리즘. 사이클 포함 X.

 -> 음의 가중치도 계산 가능. 다익스트라 알고리즘보다 시간복잡도 높음(더 느림).

 -> 간선들을 중심으로 찾음

 -> 방문되지 않은 정점(값이 무한대인 정점)에서 출발하는 간선들은 고려하지 않는다.

 -> 즉, 다익스트라의 변형을 통해 음수간선에 대한 처리 및 음수 사이클을 체크하기 위한 알고리즘.

 -> 여기서 모든 사이클을 한 번 다 돌아도 distance의 변화가 하나도 없으면 그냥 해당 for문을 종료시켜도 됨.

 ** 최악의 경우 시간복잡도 O(n^3), 보통 O(VE)

 

벨만-포드 순서. 다익스트라와 동일하다.

샘플코드

---

public static boolean bellman(int n, int m, int startPoint) {
		// 1단계 : 시작 점을 0, 나머지 점을 무한대로 만들기
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[startPoint] = 0;
		
		// 2단계 : 전체 점(n) - 1번 만큼 전체 Vertex를 탐색하기
		for(int i = 1; i < n; i++) {
			boolean isChange = false;	// 전체 간선을 돌면서 최단 경로가 새로 갱신되는지 구별하는 boolean 변수
			for(int j = 0; j < m; j++) {
				Vertex11657 vertex = graph.get(j);
				// 우선, 시작 점이 한 번도 방문하지 않았던 점이면 안되고(맨 처음 시작 점부터 해당 끝 점까지의 최단 가중치 경로를 찾아야 하기 때문에)
				// 다른 기존 경로보다 짧은 경우를 찾아야 하므로
				if(distance[vertex.getStart()] != Integer.MAX_VALUE && 
						distance[vertex.getStart()] + vertex.getWeight() < distance[vertex.getEnd()]) {
					distance[vertex.getEnd()] = distance[vertex.getStart()] + vertex.getWeight();
					isChange = true;
				}
			}
			if(!isChange) {	// 최단 경로 갱신 여부
				break;
			}
		}
		
		// 3단계 : 음수 가중치 사이클 점검
		for(int i = 0; i < m; i++) {
			Vertex11657 vertex = graph.get(i);
			// 우선, 시작 점이 한 번도 방문하지 않았던 점이면 안되고(맨 처음 시작 점부터 해당 끝 점까지의 최단 가중치 경로를 찾아야 하기 때문에)
			// 다른 기존 경로보다 짧은 경우를 찾아야 하므로
			if(distance[vertex.getStart()] != Integer.MAX_VALUE && 
					distance[vertex.getStart()] + vertex.getWeight() < distance[vertex.getEnd()]) {
				return false;	// 음의 가중치 존재
			}
		}
		
		return true;	// 음의 가중치 존재 X
	}

 

 

 

 

참고
그림 출처 : 내 알고리즘 수업 피피티

참고 사이트
https://journee912.tistory.com/68
https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/
https://bethejustice.tistory.com/32