📌 벨만-포드 알고리즘
벨만-포드(Bellman-Ford) 알고리즘은 그래프가 가중치를 가지는 방향있는 변(Edge)으로 이루어져 있을때 한 점(Vertex)에서 나머지 다른 점까지의 최단 경로를 찾는 알고리즘이다.
목표만 봤을 때 다익스트라 알고리즘과 같이 최단 경로를 구하는 알고리즘이다. 그러면 뭐가 다르냐? 바로 음의 가중치에 대해서도 최단 경로를 구할 수 있다.
앞서 다익스트라 알고리즘을 설명할 때 양의 가중치에서만 해당 알고리즘을 사용한다고 했었는데, 음의 가중치에서 다익스트라 알고리즘을 사용할 수 없는 이유는 다음과 같다.
음의 가중치 무한 순환
다음과 같은 노드가 있을 때 4번 노드로 가는 최단 경로는 1 -> 2 -> 3 -> 4이 될 것이다.
그런데 다익스트라 알고리즘 특성상 가장 작은 비용이 드는 경로를 찾기 때문에 음의 가중치인 2 -> 3 경로에서 다시, 3 -> 2로 가게되어 -2가 계속 가중되는 무한 순환이 반복되고 만다. 때문에 기존 다익스트라 알고리즘으로는 음의 가중치 문제를 풀 수 없다.
그래서,
기존의 다익스트라 알고리즘이 아닌 벨만-포드 알고리즘을 사용해 문제를 풀 수 있다. 다만, 시간 복잡도는 조금 올라간다.
다만,
음의 무한 순환에 대해 최단 경로를 찾을 수 있는 알고리즘은 아니다.
해당 알고리즘을 활용하는 것은 "벨만-포드 알고리즘을 통해 음의 무한 순환 발생을 감지할 수 있다" 라고 생각하면 된다. 물론 음의 무한 순환이 없을 경우 해당 알고리즘을 통해 최단 경로를 구할 수 있다.
벨먼-포드 알고리즘은 방향이 존재하는 유향 그래프(노빠꾸 그래프)에서만 사용이 가능하다. 그래서 거쳐간 노드는 다시 방문하지 않는다.
다익스트라와 벨만 포드 알고리즘의 차이점
다익스트라 알고리즘 | 벨만-포드 알고리즘 | |
음의 가중치 | X | O |
음의 사이클 | X | X |
시간 복잡도 | 최대 O(ElogV) | 최대 O(E * V) |
E는 간선의 갯수, V는 정점의 갯수이다.
📌 구현 과정
초기 설정
1. 정점에 대한 노드 클래스를 구현한다.
public static class Node {
public int curIdx; // 현재 노드 위치
public int nextIdx // 다음 노드 위치
public int distance; // 비용
public Node(int curIdx, int nextIdx, int distance) {
this.curIdx = curIdx;
this.nextIdx = nextIdx;
this.distance = distance;
}
}
2. 최소 비용 배열을 INF 값으로 한 번 초기화해준다.
static int INF = Integer.MAX_VALUE;
static long[] dist;
...
...
dist = new long[N + 1];
Arrays.fill(dist, INF);
dist[start] = 0;
거기에 시작되는 노드의 최소비용을 0으로 초기화해준다.
노드 탐색 과정
먼저 N(정점의 갯수) * M(간선의 갯수)만큼 반복문을 실행해준다.
// N * M 만큼 반복
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Node curNode = graph.get(j);
해당 간선이 음의 간선인지 어떻게 알 수 있을까?
먼저는 다음 노드에서 최소 비용 값이 줄어들었는지를 확인해야 한다. 아래의 조건으로 확인해볼 수 있다.
Node curNode = graph.get(j);
if (dist[curNode.curIdx] != INF && dist[curNode.curIdx] + curNode.distance < dist[curNode.nextIdx]) {
dist[curNode.nextIdx] = dist[curNode.curIdx] + curNode.distance;
dist[curNode.curIdx] != INF는 현재 노드를 방문했는지 여부를 체크한다. INF 값이 그대로 있다면 해당 위치는 방문하지 못하기 때문에 방문을 안했으므로 계속 Pass해야 한다.
음의 순환 여부 체크
if (dist[curNode.curIdx] != INF && dist[curNode.curIdx] + curNode.distance < dist[curNode.nextIdx]) {
...
...
// 음수 순환이 존재
if (i == N - 1) return true;
}
그림과 같이 음의 순환이 이루어진다면 가시적으로는 무한 반복으로 보이지만 최소 비용 배열에선 결국 음의 가중치가 계속 누적된다.
결국 모든 순환이 마쳐질 때까지(i == N - 1) if문의 조건을 만족했다면 그것은 음의 가중치가 계속 누적된다는 의미이고 이는 음의 무한 순환을 의미한다.
전반적인 코드의 내용인 이게 전부이다.
아래는 백준 Q5_11657(타임머신) 문제에 대한 풀이이다.
📌 전체 코드
package level27_최단_경로_.Q5_11657;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
/*
문제) 타임머신
N개의 도시가 있다.
그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다.
각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다.
시간 C가 양수가 아닌 경우가 있다.
C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.
1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
입력)
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다.
둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
출력)
만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다.
그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다.
만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.
시간 제한 : 1초
메모리 제한 : 256 MB
*/
public class Main {
private static class Node {
int curIdx;
int nextIdx;
int distance;
public Node(int curIdx, int nextIdx, int distance) {
this.curIdx = curIdx;
this.nextIdx = nextIdx;
this.distance = distance;
}
}
private static int INF = Integer.MAX_VALUE;
private static ArrayList<Node> graph = new ArrayList<>();
private static long[] dist;
/*
3 4 // 도시의 갯수 N, 버스 노선의 갯수 M
1 2 4 // 시작 도시 a, 도착 도시 b, 거리 c
1 3 3
2 3 -1
3 1 -2
*/
public static void main(String[] args) throws IOException{
int N = readInt();
int M = readInt();
dist = new long[N + 1];
// 노드 입력
for (int i = 0; i < M; i++) {
int a = readInt();
int b = readInt();
int c = readInt();
graph.add(new Node(a, b, c));
}
boolean negative_cycle = bellmanFord(1, N, M);
if (negative_cycle) {
System.out.println(-1);
} else {
for (int i = 2; i <= N; i++) {
if (dist[i] == INF) System.out.println(-1);
else System.out.println(dist[i]);
}
}
}
private static boolean bellmanFord(int start, int N, int M) {
Arrays.fill(dist, INF);
dist[start] = 0;
// N * M 만큼 반복
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Node curNode = graph.get(j);
if (dist[curNode.curIdx] != INF && dist[curNode.curIdx] + curNode.distance < dist[curNode.nextIdx]) {
dist[curNode.nextIdx] = dist[curNode.curIdx] + curNode.distance;
// 음수 순환이 존재
if (i == N - 1) return true;
}
}
}
return false;
}
private static int readInt() throws IOException {
boolean isNegative = false;
int value = 0;
while (true) {
int input = System.in.read();
if (input == '\n' || input == ' ') {
return (isNegative) ? -1 * value : value;
} else if (input == '-') isNegative = true;
else value = value * 10 + (input - 48);
}
}
}
댓글