[2022 1학기] 4주차 - 벨만-포드

1. 벨만 포드 알고리즘이란?

한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘

간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다. 

다익스트라 알고리즘과 달리 매 반복마다 모든 간선을 확인한다.

시간복잡도가 느리다. -> O(VE)

 

2. 동작 원리

시작점에서 한 정점 x까지의 최단 경로를 구하다고 하면,

x를 제외한 모든 노드(V-1)가 시작점과 x 사이의 최단 경로를 구성한다.

모든 정점으로 가는 최단 경로 갱신 과정을 V-1번 반복하면 된다. 

음수사이클이 있는지 알아보려면 1번 더 돌려서 최단 거리가 갱신되는지 확인하기

 

3. 코드

#define INF 987654321
typedef pair<int, int> P;

long long dist[510]; //각 도시의 거리 계산 long long 필수
vector<P> edge[510]; //간선

int N, M; //도시개수, 버스노선수


void bellman_ford(int start) {
	bool flag = false;
	dist[start] = 0;


	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < edge[i].size(); j++) {
				int next = edge[i][j].first;
				int nextCost = edge[i][j].second;

				if (dist[i] != INF && dist[next] > dist[i] + nextCost) {
					dist[next] = dist[i] + nextCost;
					if (k == N) {
						flag = true; // N번째에도 갱신이 된다면 음수 사이클이 존재
						break;
					}
						
		
				}
			}
		}
	}


	if (flag) {
		printf("-1\n"); //음수사이클이라서
	}
	else {
		for (int i = 2; i <= N; i++) {
			if (dist[i] == INF) {
				printf("-1\n");
			}
			else {
				printf("%d\n", dist[i]);
			}
		}
	}
}




int main() {
	scanf("%d %d", &N, &M);

	int a, b, c; //시작, 도착, 가중치
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &a, &b, &c);
		edge[a].push_back({ b, c });
	}


	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}


	bellman_ford(1); //1에서 시작
	  




	return 0;
}

 

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!