[C++] 벨만-포드 알고리즘 ⭐

벨만-포드(Bellman-Ford) 알고리즘은 그래프 내에서 단일 출발 노드로부터 모든 다른 노드까지의 최단 경로를 찾는 알고리즘 중 하나입니다. 벨만-포드 알고리즘은 음수 가중치를 가진 간선도 처리할 수 있으며, 음수 가중치 간선이 사이클(음의 사이클)을 형성하지 않는 경우에 사용할 수 있습니다.

 

음수 가중치 처리
벨만-포드 알고리즘은 음수 가중치를 가진 간선을 처리할 수 있습니다.
단, 음수 가중치 사이클이 없어야 합니다. 음수 가중치 사이클이 있을 경우 알고리즘은 무한 반복됩니다.

시간 복잡도
벨만-포드 알고리즘의 시간 복잡도는 O(V * E)입니다. 여기서 V는 노드의 수, E는 간선의 수를 나타냅니다.
각 노드에 대해 모든 간선을 검사하기 때문에 모든 간선을 한 번씩 확인하는 과정이 V번 반복됩니다.

 

음수 가중치 사이클 검사 🔥
벨만-포드 알고리즘은 루프의 추가 이터레이션 이후에도 최단 거리가 갱신되는지 검사합니다. 만약 한 번 더 최단 거리가 갱신된다면 이것은 음수 가중치 사이클이 그래프에 존재한다는 의미입니다.

 

📄문제

N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 한 도시에서 다른 도시로 이동하는데 쓰이는 비용의 최소값을 구하는 프로그램을 작성하세요.

 

⬇️ 입력

첫 번째 줄에는 도시의 수N(N<=100)과 도로수 M(M<=200)가 주어지고, M줄에 걸쳐 도로정보와 비용이 주어진다. 만약 1번 도시와 2번도시가 연결되고 그 비용이 13이면 “1 2 13”으로 주어진다. 그 다음 마지막 줄에 출발도시와 도착도시가 주어진다.

5 7 1 2 5 1 3 4 2 3 -3 2 5 13 3 4 5 4 2 3 4 5 7 1 5

 

⬆️ 출력

출발도시에서 도착도시까지 가는데 걸리는 최소비용을 출력한다. 음의 사이클이 존재할 경우 -1를 출력한다.

14

 

📝 풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Edge
{
	int from;
	int to;
	int weight;

	Edge(int from, int to, int weight) : from(from), to(to), weight(weight) {}

	bool operator < (const Edge& ref) const
	{
		return weight > ref.weight;
	}
};

int main()
{
	priority_queue<Edge> q;
	vector<Edge> edges; // 간선 정보를 담는 벡터
	vector<int> dist; // 가중치 누적

	int N, M, f, t, w;
	scanf_s("%d %d", &N, &M);

	dist = vector<int>(N + 1, INT_MAX);

	for (int i = 0; i < M; ++i)
	{
		scanf_s("%d %d %d", &f, &t, &w);
		edges.push_back({ f, t, w });
	}

	scanf_s("%d %d", &f, &t);
	dist[f] = 0;

	for (int i = 1; i < N; ++i) // 간선의 개수를 1개부터 증가시켜 지속적으로 갱신
		for (int j = 0; j < edges.size(); ++j) // 모든 간선을 검사
		{
			int from = edges[j].from; // 현재 위치한 곳
			int to = edges[j].to; // 다음으로 갈 곳
			int weight = edges[j].weight; // 다음으로 가기 위한 가중치

			// 만약 현재 위치의 가중치가 INT_MAX가 아니면서(다른 간선에 의해 현재 위치로 옴)
			// 현재까지의 가중치 + 다음으로 가기 위한 가중치가 저장된 가중치보다 작다면?
			if (dist[from] != INT_MAX && dist[from] + weight < dist[to])
				dist[to] = dist[from] + weight; // 가중치 갱신
		}

	// 모든 간선 정보를 한번씩 검사하여 음의 사이클이 존재하는지 확인
	for (int i = 0; i < edges.size(); ++i)
	{
		int from = edges[i].from;
		int to = edges[i].to;
		int weight = edges[i].weight;

		// 현재까지의 가중치 + 다음으로 가기 위한 가중치가 다음 위치의 저장된 가중치보다 작다면 음의 사이클이 존재
		if (dist[from] != INT_MAX && dist[from] + weight < dist[to])
		{
			printf("-1");
			exit(0);
		}
	}

	printf("%d", dist[t]);
}

• 벨만-포드 알고리즘은 각 단계에서 간선을 검사하여 지속적으로 최단 거리를 갱신합니다. 
• 만약 dist[from] + w가 dist[to]보다 작다면, dist[to]를 dist[from] + w로 업데이트합니다.
• 위의 간선 검사 및 최단 거리 갱신 단계를 모든 노드에 대해 반복합니다. 이 작업을 총 V - 1번 반복합니다. 여기서 V는 노드의 수입니다. 이렇게 하면 시작 노드에서 모든 노드까지의 최단 경로를 찾을 수 있습니다.
• 벨만-포드 알고리즘은 루프의 추가 이터레이션 이후에도 최단 거리가 갱신되는지 검사합니다. 만약 한 번 더 최단 거리가 갱신된다면 이것은 음수 가중치 사이클이 그래프에 존재한다는 의미입니다.