#include <iostream>
#include <vector>
using namespace std;
int dist[101];
struct Edge{
int s;
int e;
int val;
Edge(int a, int b, int c){
s = a;
e = b;
val = c;
}
};
int main() {
vector<Edge> Ed;
int i, n, m, a, b, c, j ,s ,e;
scanf("%d %d",&n,&m);
for(i = 1; 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;
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;
}
}
}
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;
}
특징
벨만포드는 다익스트라처럼 출발도시로부터 갈 수 있는 모든 도시까지의 최단거리를 구하는 알고리즘임
하지만, 벨만포드는 Greedy하지 않기 때문에 정렬 과정이 없음
Kruskal에서처럼 벡터에 그래프 정보를 저장하고 다익스트라처럼 dist배열에 무한대 값을 넣어놓고 최저값을 계속 할당시킴.
간선 값이 음의 값이어도 괜찮음(하지만 음의 사이클은 만들어져선 안됌)
만약 문제에서 간선값이 음의 값인데 음의 사이클에 대한 예외처리를 요구한다면? 벨만 포드일 확률이 높음.
1. distance 배열을 할당하 되, 전부 무한대로 할당해 놓는다.(다익스트라&벨만포드 고유의 방법)
struct Edge{
int s;
int e;
int val;
Edge(int a, int b, int c){
s = a;
e = b;
val = c;
}
};
for(i = 1; i <= m; i++){//그래프 생성 인접리스트
scanf("%d %d %d", &a, &b, &c);
Ed.push_back(Edge(a,b,c));
}
3. 시작노드는 dist 배열에 0으로 초기화 한다.
dist[s] = 0;
4. 벡터에 저장되어 있는 그래프 정보를 쭉 훑으면서 dist배열에 할당한다.
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]){ //u:1에서 v:2까지의 비용 < 원래저장된 v까지 비용(이전 경로횟수에서 저장된 값)
dist[v] = dist[u]+w;
}
}
4-1. 위의 코드에서 바깥쪽 for문은 굳이 왜 있는걸까?
해당 문제는 입력 순서(=Vector 저장 순서)가 정답이 도출되는 순서대로 입력되었기 때문에 문제가 없다.
하지만, 입력순서가 무조건 경로순으로 입력되어있지 않다. 예를 들어,
출발 : 3 도착 : 5 , 2 5 13 간선을 2 5 1로 수정하면 최소비용값 9가 계산되지 않는다.
만약, i가 1이고 안쪽 j for문이 2 3 -3을 가리켰다면 2는 처음에 무한대이기 때문에 3이 relax되지 않는다.
2 5 1도 2가 무한대이기 때문에 relax되지 않는다.
3이 출발노드 이므로 3은 무한대가 아닌 0이라서 3 4 5는 relax된다.
이렇게 돌리다보면, i =1 일 때, 무한대 8 0 5 12로 마무리된다.
그러면 결국 2에서 3으로 가거나 2에서 5로 가는 경로는 무시된 값이라는 것이다. 이렇게 입력 순서가 입력순서가 경로와는 다르게 꼬여서 제시된다면 경로가 무시될 수 있기 때문에
혹시 무한대여서 무시된 경로가 있나? 다시 한번 살펴볼 필요가 있다(무시된 노드에 대해서 모두 한 번씩 기회를 줘야한다.)
그래서 도착노드를 제외한 노드의 수 만큼 반복하여 무한대여서 무시당한 모든 노드에게 한 번씩 기회를 주어야 한다.
5. 음의 사이클 유무 확인
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("\n -1\n");
exit(0);
}
}
위에서 안쪽 j for문 돌린 것과 똑같이 한번 더 해보는 것이다.
위쪽에서 이미 relax가 끝났는데, 또 relax하려고한다.? 그럼 cycle이 있다는 뜻(끊임 없이 relax)이다.
