81. 벨만-포드 알고리즘

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

 

풀이 

- 벨만 포드 알고리즘은 해당 정점에 1번만에 갈 수 있는 비용, 2번만에 갈 수 있는 비용 ~ n-1번만에 갈 수 있는 비용을 비교한다.

- dist배열을 만들어 놓고 무한대 값(2147000000)으로 초기화 한다.

- 시작정점인 dist[s]=0으로 초기화 한 후 for문에 진입

- 총 1~n-1개의 정점을 거치는 경우의 수가 있기 때문에 바깥 for문은 1~n-1까지 돈다.

- 각 경우마다 모든 정점을 살펴야 함으로 안쪽 for문은 0~Ed.size()만큼 돈다.

- 시작정점, 도착정점, 비용을 다른 변수에 받아 둔 후 이를 가지고 dist배열을 변경한다.

=> dist[u](시작정점 dist값)이 무한대가 아니고 && dist[u]+w(시작정점 값+ 연결값)<dist[v](기존 값)이면 

=> dist[v]의 값을 변경한다.

- 마지막 for문은 음의 사이클이 있는지 확인 하는 절차 (n-1개의 간선을 거치는 경로가 아닌 n개의 간선을 거치는 경로가 있다면 음의 사이클이 있다는 것을 의미 한다=> 벨만포드에서는 이를 허용하지 않음)

 

 

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
int dist[101];
using namespace std;

//81. 벨만-포드 알고리즘
//간선을 한 번만에 갈 수 있다, 두 번만에 갈 수 있다 등등
//정점 5개면 간선은 4번만에 가는게 가장 긴 경로

struct Edge{
    int s;
    int e;
    int val;
    Edge(int a, int b, int c){
        s=a;
        e=b;
        val=c;
    }
};

int main(){
    int i, j, n, m, a, b, c, s, e;
    vector<Edge> Ed;
    scanf("%d %d", &n, &m); //노드, 간선
    for(i=0;i<m;i++){
        scanf("%d %d %d", &a, &b, &c);
        Ed.push_back(Edge(a,b,c));
    }
    for(i=1;i<=n;i++){
        dist[i]=2147000000;
    }
    scanf("%d %d", &s, &e);
    dist[s]=0; //출발점 0 초기화
    for(i=1;i<n;i++){
        for(j=0;j<Ed.size();j++){
            int u= Ed[j].s;
            int v= Ed[j].e;
            int w=Ed[j].val;
            if(dist[u]!=2147000000 && dist[u]+w<dist[v]){
                dist[v]=dist[u]+w;
            }
        }
    }
    //음의 사이클이 있는지 확인 (n번쨰!)
    for(j=0;j<Ed.size();j++){
        int u=Ed[j].s;
        int v=Ed[j].e;
        int w=Ed[j].val;
        if(dist[u]!=2147000000 & dist[u]+w<dist[v]){
            printf("-1\n");
            exit(0);
        }
    }
    printf("%d\n", dist[e]);
    return 0;
}