벨만 포드 알고리즘(Bellman Ford Alogorithm)
벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 최단 경로 알고리즘이다. 탐색을 하는 방식도 다익스트라와 유사하다. 다익스트라 알고리즘과의 차이점은
| 벨만 포드 알고리즘 | 다익스트라 알고리즘 |
| 음의 가중치가 간선에 있을때도 작동하며 음의 사이클도 감지함 | 음의 가중치가 간선에 있을경우 작동하지 않음 |
| 상대적으로 시간이 더 소요됨 | 벨만 포드의 알고리즘보다 시간이 덜 소요됨 |
| 시간복잡도는 O(VE) | 시간복잡도는 O(ElogV) |
[작동방식]
1. 출발 노드를 설정한다
2. 최단 거리 배열을 초기화한다.
3. 인접한 노드로 가는 간선을 탐색후 최단거리 배열을 갱신한다.
4. 3번과정을 (V-1)번 반복한다.
5. 음수 사이클의 존재 유무를 판별하려면 한 번 더 실행한다. 이때 최단거리 배열이 갱신된다면 음수 사이클이 존재하는것이다.
[예시]
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
문제 : 1번노드에서 각 노드(2번, 3번 노드)로 갈 수 있는 최단거리를 표시하고 음의 사이클이 존재하거나 갈 수 없다면 -1을 출력한다.
최단거리를 기록할 dist 배열 선언 및 초기화.
| 1 | 2 | 3 |
| INF | INF | INF |
노드가 3개이기 때문에 탐색하는 작업을 (V-1)번인 2번반복 후 마지막 음수 사이클 존재확인을 위해 1번 더 한다.
총 3번 반복한다.
1번째 반복
1번 노드기준 탐색
1번 노드 -> 2번 노드 = 1번 노드 가중치(0) + 간선의 가중치(4) = 4 < INF
1번 노드 -> 3번 노드 = 1번 노드 가중치(0) + 간선의 가중치(3) = 3 < INF
| 1 | 2 | 3 |
| 0 | 4 | 3 |
2번 노드 기준 탐색
2번 노드 -> 3번 노드 = 2번노드 가중치(4) + 간선의 가중치(-4) = 0 < 3번 노드의 가중치(3)
3번 노드의 가중치를 더 적은 0으로 변경
| 1 | 2 | 3 |
| 0 | 4 | 0 |
3번 노드 기준 탐색
3번 노드 -> 1번 노드 = 3번의 가중치(0) + 간선의 가중치(-2) = -2 < 1번 노드의 가중치(0)
더 적은 가중치인 -2로 갱신
| 1 | 2 | 3 |
| -2 | 4 | 0 |
이 과정을 2번 더 반복해주면 된다.
2번째 반복
| 1 | 2 | 3 |
| -2 | 4 | -4 |
3번째 반복
V번째 반복에서 V-1번째와의 결과와 다르다면 음의 사이클이 존재하다는 뜻이다.
| 1 | 2 | 3 |
| -4 | 4 | -8 |
2번 노드의 값은 변하지 않았지만 1, 3번노드는 음의 사이클이 존재하기 때문에 답 = -1
[전체 코드]
import java.io.*;
import java.util.*;
public class Main {
static class Edge {
int start, end, cost; // 시작 노드, 도착 노드, 가중치
public Edge(int start, int end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
}
static int v, e;
static List<Edge> edges;
static long[] dist;
public static void main(String[] args) throws Exception {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
StringBuilder sb = new StringBuilder();
v = Integer.parseInt(st.nextToken()); // 노드의 수
e = Integer.parseInt(st.nextToken()); // 간선의 수
// 리스트 선언
edges = new ArrayList<>();
// 가중치를 담을 배열
dist = new long[v + 1];
// dist 배열의 전체내용을 Long.MAX_VALUE 로 초기화
Arrays.fill(dist, Long.MAX_VALUE);
// edges 초기화
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
edges.add(new Edge(start, end, cost));
}
// 출력
if (BellmanFord()) {
// i = 2인 이유, 문제에서 0번노드부터가아닌 1번노드부터 존재
// 1번노드 제외한 나머지 노드를 출력이기 때문에
for (int i = 2; i <= v; i++) {
// 도달하지 못하는 장소일 경우 -1
if (dist[i] == Long.MAX_VALUE) {
sb.append(-1).append("\n");
continue;
}
// 도달가능할 경우 최소거리 출력
sb.append(dist[i]).append("\n");
}
} else { // 음의 사이클이 존재할 경우 -1 출력
sb.append(-1);
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
public static boolean BellmanFord() {
dist[1] = 0;
// n-1번의 반복작업과 마지막(n번째 탐색) 확인작업을 한번에 실행
for (int i = 1; i <= v; i++) {
for (Edge edge : edges) {
// 한번도 방문하지 않았다면 패스
if (dist[edge.start] == Long.MAX_VALUE) {
continue;
}
// 버스 도착점까지의 최소거리가 (시작점 + 비용) 보다 크면 갱신
if (dist[edge.end] > dist[edge.start] + edge.cost) {
dist[edge.end] = dist[edge.start] + edge.cost;
// n번째 작업에서 값이 변경되면 Negative Cycle(음의 사이클)이 존재한다는 뜻
if (i == v) {
return false;
}
}
}
}
return true;
}
}
'알고리즘' 카테고리의 다른 글
| 다익스트라 알고리즘(Dijkstra's algorithm) - 우선순위 큐 (0) | 2023.10.28 |
|---|---|
| 다익스트라 알고리즘(Dijkstra's algorithm) - 인접 행렬 (0) | 2023.10.28 |
