[C++] 벨만-포드(Bellman-ford)

 

 

 

벨만-포트(Bellman-ford) 알고리즘은 다익스트라 알고리즘과 유사하게 특정 노드로부터 그래프에서 최단 거리를 구하는 알고리즘이다. 차이점은 아래과 같다.

• Edge 가중치가 음수를 가질 수 있다.
• 음수 사이클의 존재 여부를 판단할 수 있다.
• 시간 복잡도: O(V * E)

 

 

 

벨만-포드 자료구조

 

벨만-포드는 Edge 기반으로 동작하기 때문에 엣지 리스트로 그래프를 표현한다.

엣지 리스트는 보통 Edge 구조체로 저장한다.

 

그리고 다익스트라와 마찬가지로 최단 거리를 저장하기 위한 정답 리스트가 필요하다.

시작 노드는 0으로, 나머지는 무한대에 가까운 Dummy 값으로 초기화해준다.

 

 

 

 

 

벨만-포드 원리

벨만-포드는 Edge에 대해 for문을 돌기 때문에 업데이트 반복 횟수는 (N-1) 이다.

음수 사이클이 없을 때 특정 두 노드의 최간 거리를 구성할 수 있는 Edge 최대 개수도 (N-1)이다

 

 

엣지 리스트 전체를 탐색한다. 이때 다음과 같은 조건에 해당하면 업데이트한다.

• 정답 리스트[시작 노드] 값이 무한 대가 아니다.
• 정답 리스트[시작 노드] + weight < 정답 리스트[끝 노드]

정답 리스트[끝 노드] = 정답 리스트[시작 노드] + weight으로 업데이트한다.

이것을 모든 엣지 리스트에 대해 수행한다. 이것이 하나의 업데이트 횟수이다.

 

음수 사이클이 없다면 최대 N-1 번의 업데이트로 출발 노드와 모든 노드간의 최단 거리를 구할 수 있다. 완성 후에 마지막으로 이 그래프에서 음수 사이클이 존재하는지 확인해야 한다.

 

 

 

 

 

벨만-포드 응용: 음수사이클 여부

 

음수 사이클이 존재 여부를 어떻게 판단할 수 있을까?

답은 N번째 반복에서 업데이트가 되는 노드가 발생하는지 확인하는 것이다.

만약 음수 사이클이 존재하면 사이클로 인해 가중치가 계속 감소하여 최단 거리를 구할 수 없기 때문이다.

 

 

 

 

 

벨만-포드 코드

void bellman_ford()
{
	ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

	int N, M;
	int start, end;
	cin >> N >> M;

	vector<Edge> edge_list(M + 1);
	vector<int> result(N + 1, DUMMY);
	for (int i = 1; i <= M; i++)
	{
		int start, end, weight;
		cin >> start >> end >> weight;
		edge_list[i] = Edge(start, end, weight);
	}

	cin >> start >> end;
	result[start] = 0;

	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			int s = edge_list[j].start;
			int e = edge_list[j].end;
			int w = edge_list[j].weight;

			if (result[s] != DUMMY && result[s] + w < result[e])
				result[e] = result[s] + w;
		}
	}

	cout << result[end] << endl;
}