벨만-포드
벨만-포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색한다. 음수 가중치 에지가 있어도 수행할 수 있다. 또한 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.
시간 복잡도(노드 수 : V, 에지 수 : E)
O(VE)
벨만-포드 알고리즘 핵심 이론
1. 에지 리스트로 그래프 구현하고 최단 경로 배열 초기화하기
벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다. 또한 최단 경로 배열은 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.
2. 모든 에지를 확인해 정답 배열 업데이트하기
최단 거리 배열에서 업데이트 반복 횟수는 노드 개수 -1입니다. 노드 개수가 N이고, 음수 사이클이 없을 때 특정 노드 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문이다. 특정 에지 E = (s, e, w)에서 다음 조건을 만족하면 업데이트를 실행한다.
3. 음수 사이클 유무 확인하기
음수 사이클 유무를 확인하기 위해 모든 에지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인한다. 만약 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻이 되고, 2단계에서 도출한 정답 배열이 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻이 된다. 음수 사이클이 존재하면 이 사이클을 무한하게 돌수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없다.
실제 코딩테스트에서는 벨만-포드 알고리즘을 사용해 최단 거리를 구하는 문제보다 음수 사이클을 판별하는 문제가 더 빈번하게 출제된다. 따라서 마지막에 한 번 더 모든 에지를 사용해 업데이트되는 노드가 존재하는지 확인해야 한다.
업데이트 조건과 방법
D[s] != 무한이며 D[e] > D[s] + w 일 때 D[e] = D[s] + w로 배열의 값을 업데이트한다.
음수 사이클이 없을 때 N - 1번 에지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단거리를 알려주는 정답 배열이 완성된다. 이렇게 완성 후 마지막으로 이 그래프에 음수 사이클이 존재하는지 확인해야 한다.
코드로 표현
Arrays.fill(distance, Integer.MAX_VALUE); // 최단 거리 배열 초기화하기
for(int i = 0; i < m; i++) { // 에지 리스트에 데이터 저장하기
edges[i] = new Edge(start, end, time);
}
// 벨만-포드 알고리즘 수행하기
distacne[1] = 0;
for(int i = 1; i < n; i++) { // N보다 1개 적은 수만큼 반복하기
for(int j = 0; j < m; j++) {
Edge edge = edges[j];
// 더 작은 최단 거리가 있을 때 업데이트 하기
if(distance[edge.start] != Integer.MAX_VALUE
&& distance[edge.end] > distance[edge.start] + edge.time) {
distance[edge.end] = distance[edge.start] + edge.time;
}
}
}
boolean mCycle = false;
for(int i = 0; i < m; i++) { // 음수 사이클 확인하기
Edge edge = edges[i];
if(distance[edge.start] != Integer.MAX_VALUE
&& distance[edge.end] > distance[edge.start] + edge.time) {
mCycle = true;
}
}
if(!mCycle) { // 음의 사이클이 없을 때
for(int i = 2; i <= n; i++) {
if(distance[i] == Integer.MAX_VALUE) {
System.out.println("-1");
}
else {
System.out.println(distance[i]);
}
}
}
else { // 음의 사이클이 있을 때
System.out.println("-1");
}
class Edge { // 에지 리스트를 편하게 다루기 위해 클래스로 별도 구현하기
int start, end, time; // 시작점, 도착점, 걸리는 시간
public Edge(int start, int end, int time) {
this.start = start;
this.end = end;
this.time = time;
}
}