문제 링크
문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.
1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
풀이
음수 간선이 존재하는 상황에서 최단 거리를 구하는 문제이므로 벨만-포드 알고리즘을 사용한다.
다익스트라 vs 벨만포드
노드의 개수 N, 간선의 개수 M이라 했을 때
다익스트라의 시간복잡도는 O(NlogM), 벨만포드의 시간복잡도는 O(NM)으로 다익스트라가 더 효율적이다.
하지만 다익스트라의 경우 특정 시점에서 탐색 가능한 경로 중 가장 효율적인 방향으로 탐색을 진행하는데, 이 경우 음의 간선이 존재하면 정상적으로 작동하지 않는다.
특정 시점에서 탐색이 안되는 경로에 음의 간선이 존재하고 해당 간선을 이용하는 것이 가장 효율적인 경로가 될 수 있기 때문이다.
벨만포드 작동 방식
가장 효율적인 경로를 구성하는 간선을 총 N-1개 선택해야한다.
벨만포드 알고리즘에서는 하나의 간선을 선택하기 위해 M개의 간선을 모두 확인한다.
- 초기에 시작 지점으로부터 각 지점으로 가는데 드는 비용을 무한대로 초기화한다.
- 각 간선을 확인하면서 간선의 시작지점 -> 종료지점으로 가는 비용이 해당 간선을 이용할 때 더 효율적인 경우, 그 간선을 이용한다고 가정하고 비용을 업데이트 한다.
- 이 과정을
N-1번 반복하면 최단 경로 비용을 구할 수 있다.
여기서 추가로 음의 간선이 사이클을 형성하는 경우를 찾을 필요가 있다.
N-1개의 간선을 구성한 최단 경로 상태에서 한 번 더 간선을 확인하며 더 효율적인 경로를 찾았을 때, 경로가 업데이트 된다면 그건 음의 간선 사이클이 존재한다는 의미이다.
따라서 이 문제에서는 총 N번의 사이클을 돌며 모든 간선을 확인하고 반복문이 N번째일 때 최단거리 비용이 업데이트 되는 경우 -1을 출력하도록 하였다.
코드
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
struct Link{
int a,b,c;
};
void Solve() {
int N,M; cin>>N>>M;
int a,b,c;
vector<Link> V;
for(int i=0; i<M; i++){
cin>>a>>b>>c;
V.push_back({a,b,c});
}
ll dist[N+1];
fill(dist, dist+N+1, INT_MAX);
dist[1] = 0;
for(int i=0; i<N; i++){
for(int j=0; j<V.size(); j++){
Link l = V[j];
if(dist[l.a] == INT_MAX) continue;
if(dist[l.a]+l.c < dist[l.b]) {
if(i==N-1){
cout<<-1; return;
}
dist[l.b] = dist[l.a]+l.c;
}
}
}
for(int i=2; i<=N; i++){
if(dist[i] == INT_MAX) cout<<-1<<endl;
else cout<<dist[i]<<endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
Solve();
return 0;
}