99클럽 코테 스터디 4일차 TIL - 벨만포드 알고리즘

조재훈·2024년 10월 31일

99클럽 TIL algorithm 개발자취업 코딩테스트준비 항해99

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

벨만-포드 알고리즘이란 다익스트라 알고리즘과 같이 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다

다익스트라 알고리즘과 달리 음의 가중치가 있을 때도 사용할 수 있는 알고리즘이다

다익스트라 vs 벨만-포드

위 그림에서 1번 노드에서 4번 노드로 가는 최단 거리를 구해보자

1번에서 4번으로 가는 길은 3가지가 존재한다

1 -> 3 -> 4 : 20 + (-15) = 5
1 -> 4 = 15
1 -> 2 -> 4 : 10 + 10 = 20

바로 확인할 수 있듯이 1->3->4의 경로가 최단 경로이다. 다익스트라의 경우는 1번 정점에서 2, 3, 4번으로 가는 경로를 구하면서 dist[2] = 10, dist[3] = 20, dist[4] = 15으로 dist를 업데이트 한다

그리고 다음으로 비용이 가장 작은 1->2를 선택하고 4번 노드를 탐색 후 dist[4]를 업데이트하는데 1->2->4는 20이고 1->4는 15이므로 dist[4]를 그대로 15로 둔다

4번 노드로 가는 경로가 우선순위 큐에 push되고 이제 현재 노드가 목적지니까 바로 결과를 출력하게 된다

결국 1->3->4 경로는 고려도 하지 못하게 됨

하지만 벨만-포드 알고리즘을 사용하면 모든 간선을 확인하므로 4번 노드로 가는 최단 경로를 업데이트 할 수 있다

시간 복잡도는 필요한 간선만 찾는 다익스트라와 달리(O(ElogV)) 모든 간선을 찾으니까(O(VE)) 벨만-포드가 더 소요된다

과정

벨만-포드 알고리즘의 수행 과정은 다음과 같다

출발 노드를 설정
1.1 출발 노드에서 모든 정점까지의 최단 거리를 무한대로 초기화함
그래프의 모든 간선을 V - 1번 반복하면서, 현재 간선이 최단 거리를 갱신할 수 있다면 최단 거리를 업데이트 한다
V - 1번의 반복이 끝나고, 한번 더 모든 간선을 확인하여 최단 거리 갱신이 일어난다면 음수 사이클이 존재하는 것으로 판단함

음수 사이클

그래프에서 사이클이 발생할 때 경로가 큰 음수라면 계속 순환하면서 최단 거리 테이블이 음의 무한대로 될 수 있다

구현(C++)

위의 그림을 토대로 구현해본 결과이다. 자세한 내용은 주석에 있으니 참고

#include <bits/stdc++.h>
using namespace std;

// 간선을 나타내는 구조체
struct Edge
{
	int u, v, weight;
};

int V;				// 정점 개수
int E;				// 간선 개수
int start;			// 시작 정점

vector<Edge> edges;	// 모든 간선
int dist[10];		// 최단 경로

void BellmanFord(int start)
{
	dist[start] = 0;

	// 모든 간선을 V - 1번 반복
	for (int i = 0; i < V - 1; i++)
	{
		for (int j = 0; j < E; j++)
		{
			int u = edges[j].u;
			int v = edges[j].v;
			int weight = edges[j].weight;

			// 현재 정점의 거리가 무한대가 아니고 현재 정점에서 다음 정점으로
			// 가는 거리의 합이 다음 정점의 최단 경로보다 작다면 업데이트
			if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
			{
				dist[v] = dist[u] + weight;
			}
		}
	}

	// 음수 사이클 확인
	for (int j = 0; j < E; j++)
	{
		int u = edges[j].u;
		int v = edges[j].v;
		int weight = edges[j].weight;

		// 최단 거리 갱신이 발생한다는 것은 음수 사이클이 존재함을 의미
		if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
		{
			cout << u << "->" << v << "에서 사이클 발생\n";
			return;
		}
	}

	cout << start << "번 정점부터 최단 경로 출력\n";

	// 출력
	for (int i = 1; i <= V; i++)
	{
		if(dist[i] == INT_MAX)
			cout << i << "까지 도달불가" << '\n';
		else
			cout << i << "까지 " << dist[i] << '\n';
	}
}

int main()
{
	cin >> V >> E;

	for (int i = 0; i < E; i++)
	{
		int u, v, weight;
		cin >> u >> v >> weight;
		edges.push_back({ u, v, weight });
	}

	cin >> start;

	fill(dist, dist + 10, INT_MAX);

	BellmanFord(start);
}

/*
Input
4
5
1 2 10
1 3 20
1 4 15
2 4 10
3 4 -15
1

Output
1번 정점부터 최단 경로 출력
1까지 0
2까지 10
3까지 20
4까지 5
*/