벨만-포드
그래프에서 최단 거리를 구하는 알고리즘
시간 복잡도는 O(VE)
다익스트라는 O((V+E) log V) 다익스트라보다 느리다.
기능 : 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
에지 리스트를 이용한다
특징 : 음수 가중치 에지가 있어도 수행 가능
전채 그래프에서 음수 사이클의 존재 여부를 판단 가능
1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화
typedef tuple<int,int,int> edge
최단 경로 배열은 출발 노드는 0, 나머지 노드는 ∞ 로 초기화
2. 모든 에지를 확인해 최단 거리 배열 업데이트하기
s = start, e = end, w= weight
업데이트 조건과 방법
D[s] != ∞ 이고 D[e] > D[s] + w 일 때
D[e] = D[s] + w로 업데이트.
반복 횟수는 '노드 개수 -1'
음수 사이클이 없다면 두 노드의 최단 거리를
구성할 수 있는 에지의 최대 개수는 '노드 개수 - 1'이므로
3. 음수 사이클 유무 확인
모든 에지를 한 번씩 다시 사용해 업데이트 되는
노드가 발생하는지 확인
업데이트 되는 노드가 있다면 "음수 사이클"이 있다는 뜻
2단계에서 도출한 정답 배열은 무의미
최단 거리를 찾을 수 없는 그래프임.
https://www.acmicpc.net/problem/11657
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
에지에 해당하는 이동 시간이 '0 또는 음수' -> 벨만-포드 알고리즘
시간 C가 양수가 아닌 경우가 있다!
만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서
시간을 "무한히 오래 전으로 되돌릴 수 있다면"
첫째 줄에 -1을 출력한다.
즉, 음수 사이클이 존재하면 -1 출력하면 되겠네
|
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
#include <iostream>
#include <vector>
#include <tuple>
#include <limits.h>
using namespace std;
typedef tuple<int, int, int> edge;
int n, m;
vector<long> mdistance;
// 에지리스트
vector<edge> edges;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
mdistance.resize(n + 1);
// 최단 거리 배열 무한대로 초기화
fill(mdistance.begin(), mdistance.end(), LONG_MAX);
for (int i = 0; i < m; i++)
{
int start, end, time;
cin >> start >> end >> time;
edges.push_back(make_tuple(start, end, time));
}
mdistance[1] = 0;
// 노드 개수 - 1만큼 돌린다.
for (int i = 1; i < n; i++)
{
for (int j = 0; j < m; j++)
{
edge medge = edges[j];
int start = get<0>(medge);
int end = get<1>(medge);
int time = get<2>(medge);
// 더 가까운 최단 거리가 있다면 갱신
if (mdistance[start] != LONG_MAX &&
mdistance[end] > mdistance[start] + time)
mdistance[end] = mdistance[start] + time;
}
}
// 음수 사이클을 찾아보자
bool mCycle = false;
// 에지 리스트를 한 번 더 돌린다.
for (int i = 0; i < m; i++)
{
edge medge = edges[i];
int start = get<0>(medge);
int end = get<1>(medge);
int time = get<2>(medge);
if (mdistance[start] != LONG_MAX &&
mdistance[end] > mdistance[start] + time)
{
// 업데이트가 된다면 음수 사이클이 존재
mCycle = true;
}
}
if (!mCycle)
{
for (int i = 2; i <= n; i++)
{
if (mdistance[i] == LONG_MAX)
{
cout << -1 << '\n';
}
else
{
cout << mdistance[i] << '\n';
}
}
}
else
cout << -1 << '\n';
return 0;
}
|
cs |