Bellman-Ford

작성일 | In | views

벨만 포드 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define ll long long
#define pil pair<int,ll>
using namespace std;

ll dist[501];
vector<pil> graph[501];

//음의 사이클이 발생하면 false 리턴. n:정점 개수.
bool bellman_ford(int n)
{
    fill(dist+1,dist+1+n,1e18); dist[1] = 0;
    int loop=n-1;
    while(loop--)
        for(int s=1;s<=n;s++)
            for(pil go:graph[s])
                if(dist[s]!=1e18)
                    dist[go.first]=min(dist[go.first],dist[s]+go.second);

    //한번더 돌아서 값이 갱신되면, 음의 사이클이 존재하는 것.
    for(int s=1;s<=n;s++)
        for(pil go:graph[s])
            if(dist[go.first]>dist[s]+go.second&&dist[go.first]!=1e18)
                return false;

    for(int i=2;i<=n;i++)
        printf("%lld\n",dist[i]==1e18?-1ll:dist[i]);
    return true;
}

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    while(m--)
    {
        int a,b;ll c;
        scanf("%d %d %lld",&a,&b,&c);
        graph[a].push_back({b,c});
    }
    bool ok=bellman_ford(n);
    if(!ok) printf("-1");
    return 0;
}

시간복잡도

$O(VE)$

V : 정점 수, E : 간선 수

관련문제

백준11657 : 타임머신