벨만 포드 알고리즘 Bellman Ford
벨만 포드 알고리즘 Bellman Ford
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
벨만 포드 알고리즘은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. (One To All)
다익스트라 알고리즘과 비슷하지만, 가장 큰 차이점은 가중치가 음수인 간선이 있어도 사용할 수 있다는 점이다.
또한 가중치의 합이 음수가 되는 사이클이 존재하면, 최단 거리가 무한히 작아지므로 이를 감지할 수 있다.
과정
알고리즘은 완화(Relaxation)라는 과정을 반복한다. V는 노드의 개수이다.
- 출발점의 거리는 0, 나머지 모든 정점까지의 거리는 무한대로 설정한다.
- 모든 간선을 하나씩 확인하며 최단 거리 테이블을 갱신한다. 이 과정을 V-1번 반복한다.
- dist[to] = min(dist[to], dist[from] + weight(from, to))
- 모든 정점을 거쳐가는 최단 경로는 최대 V-1개의 간선을 가질 수 있기 때문에 이 횟수만큼 반복한다.
- V번째 반복에서도 최단 거리 테이블이 갱신된다면, 그래프에 음수 사이클이 존재한다는 의미이다.
시간 복잡도
V번의 루프에서 매번 E개의 간선을 확인하므로, 시간 복잡도는 $O(VE)$가 된다.
백준 11657번 타임머신
https://www.acmicpc.net/problem/11657
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
#include <iostream>
#include <vector>
const long long INF = 1e18;
struct edge
{
int from;
int to;
int weight;
};
bool bellman_ford(int n, int m, std::vector<edge>& edges, std::vector<long long>& dist)
{
dist[1] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < m; j++)
{
int from = edges[j].from;
int to = edges[j].to;
int weight = edges[j].weight;
if (dist[from] != INF && dist[to] > dist[from] + weight)
{
dist[to] = dist[from] + weight;
if (i == n) return true;
}
}
}
return false;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<edge> edges(m);
std::vector dist(n + 1, INF);
for (int i = 0; i < m; i++)
{
std::cin >> edges[i].from >> edges[i].to >> edges[i].weight;
}
if (bellman_ford(n, m, edges, dist))
{
std::cout << -1;
}
else
{
for (int i = 2; i <= n; i++)
{
if (dist[i] == INF)
{
std::cout << -1 << '\n';
}
else
{
std::cout << dist[i] << '\n';
}
}
}
return 0;
}
SPFA (Shortest Path Faster Algorithm)
SPFA는 벨만 포드 알고리즘의 비효율성을 개선한 최적화 버전이다.
벨만 포드는 모든 간선을 무조건 V - 1번 확인하지만, SPFA는 최단 거리가 갱신된 정점과 연결된 간선만 확인하는 전략을 사용한다.
이를 위해 큐를 사용하여 최단 거리가 갱신된 정점을 관리하고, 큐에 정점이 들어있는지 여부를 배열로 관리하고, 정점이 큐에 들어간 횟수를 세는 배열을 사용하여 음수 사이클을 감지한다.
과정
- 시작 정점을 큐에 넣는다.
- 큐가 빌 때까지 다음을 수행한다.
- 큐에서 정점 cur를 꺼낸다.
- cur와 연결된 모든 이웃 정점 adj에 대해 완화를 시도한다.
- 만약 adj의 거리가 짧아졌고, 현재 큐에 들어있지 않다면 adj를 큐에 넣는다.
- 특정 정점이 큐에 들어간 횟수가 V번 이상이면 음수 사이클이 존재하는 것이다.
시간 복잡도
평균적으로 $O(E)$ 혹은 $O(V + E)$의 시간 복잡도를 가지지만, 최악의 경우 벨만 포드와 동일하게 $O(VE)$가 될 수 있다.
동일한 백준 문제에 대한 SPFA 구현
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
90
91
92
93
94
95
96
97
#include <iostream>
#include <queue>
#include <vector>
const long long INF = 1e18;
struct edge
{
int to;
int weight;
};
bool spfa(int n, int m, std::vector<std::vector<edge>>& graph, std::vector<long long>& dist)
{
std::vector count(n + 1, 0);
std::vector inQue(n + 1, false);
std::queue<int> que;
int start = 1;
dist[start] = 0;
que.push(start);
inQue[start] = true;
count[start]++;
while (!que.empty())
{
int cur = que.front();
que.pop();
inQue[cur] = false;
for (const auto& edge : graph[cur])
{
int to = edge.to;
int weight = edge.weight;
if (dist[to] > dist[cur] + weight)
{
dist[to] = dist[cur] + weight;
if (!inQue[to])
{
que.push(to);
inQue[to] = true;
count[to]++;
if (count[to] >= n)
{
return true;
}
}
}
}
}
return false;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector graph(n + 1, std::vector<edge>());
std::vector dist(n + 1, INF);
for (int i = 0; i < m; i++)
{
int a, b, c;
std::cin >> a >> b >> c;
graph[a].push_back({b, c});
}
if (spfa(n, m, graph, dist))
{
std::cout << -1;
}
else
{
for (int i = 2; i <= n; i++)
{
if (dist[i] == INF)
{
std::cout << -1 << '\n';
}
else
{
std::cout << dist[i] << '\n';
}
}
}
return 0;
}
참고
This post is licensed under CC BY 4.0 by the author.