[Algorithm/Graph] 벨만-포드 알고리즘(Bellman-Ford algorithm)과 음수 가중치 사이클 찾기

벨만 포드 알고리즘

• 그래프의 모든 에지에 대해 다익스트라의 그리디 선택 방법을 (V - 1)번 반복하여 점진적으로 최단 거리를 찾는다 (V는 정점의 개수)
• 음수 가중치가 있는 그래프를 다룰 때 벨만 포드 그래프를 사용할 수 있다.
• 다익스트라 알고리즘에 비해 높은 점근적 시간 복잡도를 가지지만, 다익스트라 알고리즘이 잘못 해석할 수 있는 그래프에 대해서도 정확한 결과를 제공한다.

 

벨만-포드 알고리즘 구현

각 정점의 최단 거리 값 배열을 반환하는 함수

struct Edge
{
	int src;
	int dst;
	int weight;
};

const int UNKNOWN = INT_MAX;

vector<int> BellmanFord(vector<Edge> edges, int V, int start)
{
	vector<int> distance(V, UNKNOWN);
	distance[start] = 0;

	// (V - 1)번 반복
	for (int i = 0; i < V - 1; i++)
	{
		// 전체 에지에 대해 반복
		for (auto& e : edges)
		{
			// 에지의 시작 정점의 거리 값이 UNKNOWN이면 스킵
			if (distance[e.src] == UNKNOWN)
				continue;

			// 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
			// 거리 값을 업데이트함.
			if (distance[e.dst] > distance[e.src] + e.weight)
			{
				distance[e.dst] = distance[e.src] + e.weight;
			}
		}
	}

	return distance;
}

• 각 루프에서 전체 에지를 검토하면서 각 정점의 거리 값을 업데이트 한다.
• 그러나 여기서 한 가지 더 고려해야 할 사항이 있다.

벨만 포드 알고리즘과 음수 가중치 사이클

음수 가중치 사이클은 에지 가중치의 합이 음수가 되는 사이클을 의미한다. 그래프에 음수 가중치 사이클이 있을 경우 해당 사이클이 반복적으로 계산에 사용되어 최종 결과가 왜곡될 수 있다.

 

벨만-포드 알고리즘의 마지막 단계에서 다시 한 번 전체 에지를 검사하여 음수 가중치 사이클이 존재하는지 알아낼 수 있다.

각 에지의 시작 정점 거리 값과 에지 가중치의 합이 해당 에지의 목적지 정점 거리 값보다 작은지를 검사해서 더 짧은 경로가 발견된다면 음수 가중치 사이클이 존재한다고 생각할 수 있다.

ex) 8 + (-3) = 5 // 8 + (-3) +  1 + (-3)  = 3 // ) 3인 경우 음수 가중치 사이클을 1번 돌았음을 알 수 있다.

 

음수 가중치 사이클을 찾아내는 벨만 포드 알고리즘 구현(C++)

vector<int> BellmanFord(vector<Edge> edges, int V, int start)
{
	vector<int> distance(V, UNKNOWN);
	distance[start] = 0;

	// (V - 1)번 반복
	for (int i = 0; i < V - 1; i++)
	{
		// 전체 에지에 대해 반복
		for (auto& e : edges)
		{
			// 에지의 시작 정점의 거리 값이 UNKNOWN이면 스킵
			if (distance[e.src] == UNKNOWN)
				continue;

			// 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
			// 거리 값을 업데이트함.
			if (distance[e.dst] > distance[e.src] + e.weight)
			{
				distance[e.dst] = distance[e.src] + e.weight;
			}
		}
	}

	// 음수 가중치 사이클이 있는 지 검사
	for (auto& e : edges)
	{
		if (distance[e.src] == UNKNOWN)
			continue;

		if (distance[e.dst] > distance[e.src] + e.weight)
		{
			cout << "음수 가중치 사이클 발견!" << endl;
			return {};
		}
	}

	return distance;
}

 

당연한 말이지만 음수 가중치가 존재하지 않는 그래프의 경우 다익스트라 알고리즘이 더 효율적이다