[Algorithm] 벨만-포드

tngus2sh·2024년 8월 11일

alogrithm

Algorithm

목록 보기

10/18

벨만-포드 알고리즘

그래프 최단 거리 구하는 알고리즘
1. 다익스트라(Dijkstra)
2. 벨만-포드(Bellman-Ford)
3. 플로이드-와샬(Floyd-Warshall)

시작정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

✔️ 음수 가중치를 허용

✔️ DP 사용, relaxation 기법

**Relaxation** 최적화 문제를 해결하는 알고리즘에서 사용되는 개념 현재까지 알려진 최단 경로의 길이를 업데이트하는 과정을 말한다. 최단 경로 문제에서는 시작점에서 각 정점까지의 최단 경로의 길이를 계산하는 것이 목표이다. 벨만-포드 알고리즘에서는 간선들을 반복하여 relaxation을 수행한다. 간선 (u,v)에 대해 relaxation을 수행할 때, 현재까지 알려진 정점 u에서 정점 v까지의 최단경로보다 더 짧은 경로를 찾으면 해당 최단 경로를 업데이트한다. 따라서, 현재까지 알고 있는 최적해를 계속해서 개선해 나가는 과정

다익스트라와 차이점

	다익스트라	벨만-포드
음수 가중치	X	O
음수 사이클	X	X
시간복잡도	O(mlogn)	O(mn)

주의사항

음수 사이클이 없어야 한다.

**음수 사이클** 가장 싼 톨비로 목적지까지 가는 알고리즘을 만들기 위해 고속도로를 그래프로 만든다고 생각해보자. 톨게이트에서 톨비 100원을 받는 대신에 100원을 준다고 하면? 그리고 이 톨케이트에서 나오자마자 다시 돌아가서 계속 반복으로 이 돈을 받을 수 있다면? 그렇다면 톨게이트를 뺑글뺑글 도는 것만으로도 무한으로 돈을 받을 수 있을 것이고 톨비는 계속 줄어들 것이다. 이게 바로 음수 사이클이다. 다시 말해, 사이클의 가중치 합이 음수인 경우를 말한다.

과정

`dist`는 출발지로부터 최단거리를 기록하는 1차원 배열이다. 출발지는 0, 나머지는 INF(=무한)으로 초기화한다. 정점의 개수 N만큼 아래를 반복한다. 1. 간선 m개를 하나씩 모두 살펴본다. 현재 간선의 가중치를 `cost(v, w)`라고 한다면 나오는 정점은 v, 들어오는 정점은 w이다. `dist[v]`는 지금까지 계산한 출발지에서 v까지 최소거리이다. `dist[v]`가 무한대가 아니라면 2)를 진행한다. 2. `dist[v]` = min(①, ②) ① `dist[v]` : 지금까지 계산한 v에 도착하는 최단거리 ② `dist[w]` + `cost(w, v)` : w에 도착하는 최단거리 + w에서 v로 가는 간선의 가중치

설명 아래 그림은 정점의 개수 n=5이다. n=1부터 n=5까지 간선을 모두 살펴보며 dist를 업데이트한다. 간선의 개수는 m=9이다. 출발 정점은 4로 한다. 1) n = 1 dist의 배열에 무한이 아닌 값은 4이다. v = 4인 정점만 살펴본다.
- dist[4] = 0
  - dist[1] = 8
```
    ① `dist[1]`= 무한
    
    ② `dist[4]` + `cost(4, 1)` = 0 + 8 = 8
    
    ① > ② 이므로 값 갱신
    
- `dist[5] = 2`
    
    ① `dist[5]` = 무한
    
    ② `dist[4]` + `cost(4, 5)` = 0 + 3 = 3
    
    ① > ② 이므로 값 갱신
    
```
  2) n = 2
  
  dist의 배열에 무한이 아닌 값은 1, 4, 5이다. v = 1, 4, 5인 간선만 본다.
- dist[4] = 0 갱신 X
- dist[1] = 8
  - dist[2] = 18 ① dist[2]= 무한 ② dist[1] + cost(1, 2) = 8 + 10 = 18 ① > ② 이므로 값 갱신
  - dist[3] = 5 ① dist[3] = 무한 ② dist[1] + cost(1, 3) = 8 + 5 = 13 ① > ② 이므로 값 갱신
- dist[5] = 2
  - dist[4] 갱신 X
```
    ① `dist[4]`= 0
    
    ② `dist[5]` + `cost(5, 4)` = 3 + 9 = 12
    
    ① < ② 이므로 값 갱신 X
    
- `dist[2]` 갱신 X
    
    ① `dist[2]` = 18
    
    ② `dist[5]` + `cost(5, 2)` = 3 + 31 = 34
    
    ① < ② 이므로 값 갱신 X
    
```
  3) n = 3
  
  dist의 배열에 무한인 값이 없으므로 모든 간선을 위의 방식대로 살펴본다. n = 5까지 반복한다.
  
  최종 모습)
  
  음수 사이클 확인하기
  
  위 그림처럼 음수 가중치가 포함된 사이클이 있으면 음수 사이클이 존재하는 것이다. 벨만-포드 알고리즘에서 정점 n개 만큼 반복하는 과정을 한 번 더 진행한다. 이 때 바뀌는 값이 있다면 음수 사이클이 존재하는 것이다.

구현

간선을 리스트로 묶어 구현

상세 구현

Edge 클래스를 만든다. 이 클래스는 그래프를 구현할 때 간선정보를 리스트에 저장하기 위함이다.

class Edge {
	int v; // 나가는 정점
	int w; // 들어오는 정점
	int cost;

	public Edge(int v, int w, int cost) {
		this.v = v;
		this.w = w;
		this.cost = cost;
	}
}

int dist 배열을 만든다.

dist 배열은 출발지로부터 거리가 얼마나 되는지 기록한다. dist 배열은 INF(무한대) 값으로 초기화한다.

int[] dist = new int[n + 1];
Arrays.fill(dist, INF);
dist[start] = 0;

정점의 개수 n만큼 간선을 모두 살펴본다.

1) 간선 하나 가져온다.

Edge edge = graph.get(j); 
/*
edge.v : v, 정점에서 나가는 간선
edge.w : w, 정점으로 들어오는 간선
edge.cost : cost(v, w), v -> w 가중치
*/

2) cost(v, w)에서 dist[v]가 있는지 확인한다. 즉, 출발지에서 정점 v까지 가는 거리가 있는지 확인한다. 무한이 아니라면 둘을 비교한다.

① dist[w] : 지금까지 계산한 출발지에서 w까지 최소 거리

② dist[v] + cost(v, w) : 출발지에서 v까지 가고 w까지 가는 거리

① < ② 라면 ①값을 갱신해준다.

아래는 1)과 2)를 합친 코드이다.

//정점의 개수만큼 반복
for (int i = 0; i < n; i++) {
	//간선 모두 본다
	for (int j = 0; j < m; j++) {
		Edge edge = graph.get(j); //현재 간선
		
		//현재 간선의 들어오는 정점에 대해 비교
		if (dist[edge.v] != INF && dist[edge.w] > dist[edge.v] + edge.cost) {
			dist[edge.w] = dist[edge.v] + edge.cost;
		}
	}
}

음수 가중치 확인은 모든 간선을 한 번 더 살펴보면서 dist를 살펴본다. 만약 더 작은 값이 생긴다면 음수 사이클이 존재하는 것이다.

//n번 반복 후 음수 가중치 확인
for (int i = 0; i < m; i++) {
	Edge edge = graph.get(i); //현재 간선
	
	//현재 간선의 들어오는 정점에 대해 비교 -> 더 작은 값 생기면 음수 사이클 존재
	if (dist[edge.v] != INF && dist[edge.w] > dist[edge.v] + edge.cost) {
		System.out.println("음수 사이클 존재");
		return false;
	}
}

전체 코드

class Edge {
	int v; // 나가는 정점
	int w; // 들어오는 정점
	int cost;

	public Edge(int v, int w, int cost) {
		this.v = v;
		this.w = w;
		this.cost = cost;
	}
}

public class Main {
	static ArrayList<Edge> graph;
	static final int INF = 1000000000;
	
	//정점의 개수, 간선의 개수, 출발지
	public static boolean BellmanFord(int n, int m, int start) {
		int[] dist = new int[n + 1];
		Arrays.fill(dist, INF);
		dist[start] = 0;

		//정점의 개수만큼 반복
		for (int i = 0; i < n; i++) {
			//간선의 개수만큼 반복
			for (int j = 0; j < m; j++) {
				Edge edge = graph.get(j); //현재 간선
				
				//현재 간선의 들어오는 정점에 대해 비교
				if (dist[edge.v] != INF && dist[edge.w] > dist[edge.v] + edge.cost) {
					dist[edge.w] = dist[edge.v] + edge.cost;
				}
			}
		}
		
		//음수 가중치 확인
		for (int i = 0; i < m; i++) {
			Edge edge = graph.get(i); //현재 간선
			
			//현재 간선의 들어오는 정점에 대해 비교 -> 더 작은 값 생기면 음수 사이클 존재
			if (dist[edge.v] != INF && dist[edge.w] > dist[edge.v] + edge.cost) {
				System.out.println("음수 사이클 존재");
				return false;
			}
		}
		
		//출력
		for (int i = 1; i < dist.length; i++) {
			if (dist[i] == INF)
				System.out.print("INF ");
			else
				System.out.print(dist[i] + " ");
		}
		
		return true;
	}

	public static void main(String[] args) throws IOException {
    
    //그래프 입력받기
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		// 정점의 개수, 간선의 개수 
		int n = Integer.parseInt(bf.readLine());
		int m = Integer.parseInt(bf.readLine());

		graph = new ArrayList<>();

		StringTokenizer st;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());

			graph.add(new Edge(v, w, cost));
		}
		
    //벨만-포드 알고리즘 수행
		BellmanFord(n, m, 4);
	}
}

입력
5
9
1 2 10
1 3 5
2 3 2
3 1 1
3 2 13
4 1 8
4 5 3
5 4 9
5 2 31

출력결과
8 18 13 0 3

음수 사이클있는 그래프
입력
5
9
1 2 -10
1 3 5
2 3 2
3 1 1
3 2 13
4 1 8
4 5 3
5 4 9
5 2 31

출력 결과
음수 사이클 존재

시간복잡도

$O(mn)$

tngus2sh

백엔드 개발자

이전 포스트

[Algorithm] 다익스트라

다음 포스트