1. 벨만-포드 알고리즘
•
가중치가 음수인 경우에도 사용 가능한 최단거리를 구하는 알고리즘
•
한 노드에서 다른 노드까지의 최단 거리를 구할 수 있다.
•
음수 싸이클의 발생 여부를 파악할 수 있다.
2. 벨만-포드 알고리즘 동작 원리
벨만 포드 알고리즘을 통해 최단 거리를 구하는 방식은
계속해서 모든 간선을 이용하여 a정점에서 b정점으로 갈 때, 거리가 짧아지는 경우가 생긴다면 계속 업데이트를 해주는 방식이다.
V(정점)*E(간선)번 반복후 종료 된다.
3. 벨만-포드 알고리즘 프로세스
1.
시작 정점을 결정한다.
2.
시작 정점부터 다른 정점까지 거리 값 모두 무한대로 초기화한다. (시작 정점은 0으로 초기화)
3.
현재 정점의 모든 인접 정점들을 탐생하며, 기존에 기록된 인접 정점까지의 거리보다 현재 정점을 거쳐 인접 정점에 도달하는 거리가 더 짧다면 인접 정점까지의 거리를 갱신한다.
4.
3번 과정을 V−1번 반복한다.
(최단 경로는 사이클을 포함할 수 없다. 따라서 최대 V - 1개의 간선만 사용할 수 있다. 따라서 거리를 갱신하는 과정을 V-1번 수행하게 된다면 최단거리를 얻어낼 수 있다.)
5.
위 과정을 모두 마친 후에도 거리가 갱신되는 경우가 있다면 그래프에 음수 사이클이 존재한다는 것을 알 수 있다.
3.1 BFS 시간 복잡도
V−1번 인접한 모든 간선들을 검사하는 과정을 거치기 때문에 벨만-포드 알고리즘의 시간 복잡도는 O(VE)가 된다. 시간 복잡도가 O(ElogE)였던 다익스트라 알고리즘에 비해서 복잡도가 더 크기는 하지만, 그래프에 음수 간선이 존재할 때 사용할 수 있다는 점, 음수 사이클 존재 여부를 판별할 수 있다는 점에서 유용하게 활용할 수 있는 알고리즘이다.
3.2. 벨만-포드 알고리즘 구현
void bellman() {
dist[1] = 0;
int flag = 0;
for (int k = 0; k < N; k++) {
for (int i = 1; i <= N; i++) { // 모든 정점에 대해
for (auto data : v[i]) { // 연결된 간선
if (dist[i] != INF && dist[data.first] > dist[i] + data.second) {
dist[data.first] = dist[i] + data.second;
if (k == N - 1) flag = 1;
}
}
}
}
if (flag) cout << "싸이클 발생";
}
C++
복사
