개념
최단 거리 문제 종류
- 모든 간선이 양수인 경우 - 다익스트라 알고리즘
- 음수 간선이 있는 경우 - 벨만 포드 알고리즘
- 음수 간선 순환이 없는 경우 - 다익스트라 O
- 음수 간선 순환이 있는 경우 - 다익스트라 X
벨만 포드 알고리즘
- 시간 복잡도: O(VE) - 다익스트라 알고리즘에 비해 느림
- 동작과정 간단 요약
- 출발 노드 설정 & 최단 거리 테이블 초기화
- 아래 과정을 N-1번 반복
- 전체 간선 E개를 하나씩 확인 ( 다익스트라는 특정 노드에 붙어있는 간선만 확인함 )
- 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
- 만약, 음수 간선 순환이 발생하는지 체크하고 싶다면, N-1 반복을 다시 한 번 더 수행
- 이때, 최단 거리 테이블이 갱신된다면 음수 간선이 존재하는 것
vs 다익스트라 알고리즘
- 다익스트라 알고리즘
- 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
- 음수 간선이 없다면 최적 해 찾기 가능
- 벨만 포드 알고리즘
- 매번 모든 간선을 전부 확인
- 따라서 다익스트라의 알고리즘에서의 최적 해를 항상 포함
- 다익스트라의 알고리즘에 비해 시간이 오래 걸리지만 음수 간선 탐지 가능
- 매번 모든 간선을 전부 확인
코드
1. 가중치 그래프 생성
간선 관점으로 가중치 그래프 입력
//1. 가중치 그래프 생성
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int start = sc.nextInt();
ArrayList<Edge> edges = new ArrayList<>();
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
edges.add(new Edge(a,b,c));
}
2. 최단 거리 테이블 초기화
//2. 최단 거리 테이블
int[] d = new int[n+1];
Arrays.fill(d, MAX);
3. 반복문처리 진행
노드 개수 V-1번 만큼 전체 간선을 확인
- 전체 간선 E개를 하나씩 확인 ( 다익스트라는 특정 노드에 붙어있는 간선만 확인함 )
- 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
//V-1 만큼 반복
for(int i=1; i< n; i++){
//모든 간선 확인
for(Edge e : edges){
//현재 노드 최단 거리 비용 + 간선 비용 vs 다음 노드 최단 거리 비용
if(d[e.e] > d[e.s] + e.w){
d[e.e] = d[e.s] + e.w;
}
}
}
4. 음의 사이클 존재 확인
마지막으로 최단 거리 테이블을 확인했을 때, 갱신된다면 음의 사이클이 존재하는 것
//4. 음의 사이클 존재 여부 확인 - 한번이라도 갱신되면 음의 사이클이 존재하는 것
boolean hasCycle = false;
for (Edge e : edges) {
if (d[e.s] != MAX && d[e.s] + e.w < d[e.e]) {
hasCycle = true;
break;
}
}
5. 결과 확인
//5. 결과 확인: 최단 거리 테이블 출력
if (hasCycle) {
System.out.println("Graph contains a negative weight cycle");
} else {
// 결과 확인: 최단 거리 테이블 출력
for (int i = 1; i <= n; i++) {
if (d[i] == MAX)
System.out.print("Infinity ");
else
System.out.print(d[i] + " ");
}
}
전체 코드
public class struct {
static final int MAX = 999;
public static void main(String[] args) throws IOException {
//1. 가중치 그래프 생성
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int start = sc.nextInt();
ArrayList<Edge> edges = new ArrayList<>();
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
edges.add(new Edge(a,b,c));
}
//2. 최단 거리 테이블
int[] d = new int[n+1];
Arrays.fill(d, MAX);
//3. 시작 노드 초기화
d[start] = 0;
//4.정점 개수 - 1 만큼 반복
for(int i=1; i< n; i++){
//모든 간선 확인
for(Edge e : edges){
//현재 노드 최단 거리 비용 + 간선 비용 vs 다음 노드 최단 거리 비용
if(d[e.e] > d[e.s] + e.w){
d[e.e] = d[e.s] + e.w;
}
}
}
//5. 음의 사이클 존재 여부 확인 - 한번이라도 갱신되면 음의 사이클이 존재하는 것
boolean hasCycle = false;
for (Edge e : edges) {
if (d[e.s] + e.w < d[e.e]) {
hasCycle = true;
break;
}
}
//6. 결과 확인: 최단 거리 테이블 출력
if (hasCycle) {
System.out.println("Graph contains a negative weight cycle");
} else {
// 결과 확인: 최단 거리 테이블 출력
for (int i = 1; i <= n; i++) {
if (d[i] == MAX)
System.out.print("Infinity ");
else
System.out.print(d[i] + " ");
}
}
}
static class Edge{
int s;
int e;
int w;
public Edge(int s, int e, int w){
this.s=s;
this.e = e;
this.w = w;
}
}
}
'코딩테스트 > 알고리즘' 카테고리의 다른 글
12. 그래프 - 위상 정렬 (0) | 2024.04.02 |
---|---|
11. 그래프 - 무방향 그래프 사이클 판별, 최소 신장 트리 (0) | 2024.04.02 |
10. 그래프 - 최단 경로 알고리즘(다익스트라, 플로이드 워셜) (0) | 2024.04.02 |
9. 그래프 - 그래프 탐색(DFS/BFS) (0) | 2024.04.02 |
8-2. 바이너리 인덱스 트리(BIT) (= 펜윅 트리 ) (0) | 2024.04.02 |