[c++]벨만포드 알고리즘 - 백준 타임머신 11657

벨만포드 알고리즘이란?

벨만포드 알고리즘이란 음의 가중치가 존재할 때 최단 경로를 구하는 알고리즘이다. 

양의 가중치만이 존재할 때 다익스트라 알고리즘을 이용해 최단 경로를 구한 것과는 다르게 벨만포드에는 음의 가중치가 존재한다.

 

다익스트라 알고리즘은 현재 선택한 것이 최선의 선택이라는 greedy알고리즘을 기반으로 한다. 

하지만 음의 가중치가 존재한다면 음의 가중치를 여러번 지날 수록 최단 경로는 오히려 줄어들게 되는 경우가 존재한다. 

따라서 greedy 알고리즘에 위배된다. 

 

특징

• 음의 가중치를 가지는 간선도 가능하다.
• 음의 사이클의 존재 여부를 확인할 수 있다. 
• 최단 거리를 구하기 위해서 v-1번 E개의 모든 간선을 확인한다.(다익스트라가 노드 중심의 알고리즘이라면 벨만포드는 간선 중심이다.)
• 총 연산횟수는 VxE이다. 따라서 시간 복잡도는 O(VE)이다. 
• V 번째 모든 간선을 확인하였을 때 거리 배열이 갱신 된다면 그래프 G는 음의 사이클을 갖는 그래프이다. -> 무의미 진행할수록 계속 줄어든다. 
• V-1 -> V번째로 갔을 때 변화하는 노드는 음의 cycle에 포함되는 노드이다. 
• simple path의 간선의 최대 길이를 넘어가면 사이클이 생긴 것이다. 

음의 가중치가 있을 땐 다익스트라 알고리즘이 통하지 않는다.

벨만포드 알고리즘의 수행 과정

벨만포드 알고리즘의 수행과정

생각해봐야 할 것

• 사이클을 갖는 지 갖지 않는 지 판별 할 flag가 하나 있어야할 거 같다.
• 다익스트라와 마찬가지로 인접행렬이 존재해야할 거 같다. 
• 처음 초기화는 다익스트라와 마찬가지로 무한대 값을 넣어주어야 할 거 같다.
• 사이클이 있는 지 확인하기 위해 N-1번을 돌린 후 한 번 더 돌려서 최단 경로에 변화가 있는 지를 판별해야할 거 같다.

 

문제

입 출력

풀이

#include <cstdio>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
struct Edge {
	int start; // 시작 노드
    int dest; // 도착 노드
    int cost; // 비용
}
int N,M;
vector<Edge> Edges;
int dist[502]; // 갱신할 거리 배열
void input() {
	scanf("%d %d", &N, &M);
    
    for(int i=0; i < M; i++) {
    	int a,b,c;
        scanf("%d %d %d", &a,&b,&c); // a 시작도시 b 도착 도시 c 비용
        Edges.push_back({a,b,c});
    }
}

void BellmanFord() {
	for(int i=1; i < N; i++ ) {
    	dist[i] = INF;
    } // 거리 배열 무한대로 초기화
    
    bool isNegCycle = false;
    dist[1] = 0; // 시작 노드
    //N-1번 돌린다.
    for(int i=1; i < N; i++) {
    	for(int j=0; j < M; j++) {
        	//방문한 적이 있는 노드이고 도착 지점까지 거리가 현재 노드 + 코스트 보다 크다면 더 적은 거리로 업데이트 해준다.
        	if(dist[Edges[j].start] != INF && dist[Edges[j].dest] > dist[Edges[j].start] + Edges[j].cost) {
            	dist[Edges[j].dest] = dist[Edges[j].start] + Edges[j].cost;
            }
            else continue;
        }
    }
    //N번째에 거리가 업데이트 된다면 음의 사이클을 갖는 것이다. 
    for(int i=0; i < M; i++) {
    	if(dist[Edges[i].start] != INF && dist[Edges[i].dest] > dist[Edges[i].start] + Edges[i].cost) {
        	isNegCycle = true;
            dist[Edges[i].dest] = dist[Edges[i].start] + Edges[i].cost;
        }
        else continue;
    }
    if(isNegCycle) {
    	puts("-1");
    } else {
    	for(int i=2; i<=N; i++){
        	printf("%d\n", dist[i] == INF ? -1 : dist[i]);
        }
    }
}

int main() {
	input();
    BellmanFord();
    
    return 0;
}