[알고리즘/Java] 벨만-포드(Bellman-Ford) 알고리즘

go_go_·2022년 8월 8일
알고리즘
2

알고리즘

목록 보기
8/12
post-thumbnail

✔ 목차

  1. 벨만-포드 알고리즘이란?
  2. 벨만-포드 알고리즘 과정
  3. 벨만-포드 알고리즘 구현 - Java

🔎 벨만-포드 알고리즘이란?

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

벨만포드(Bellman-Ford) 알고리즘

  • 그래프 최단 경로 구하는 알고리즘
  • 하나의 정점에서 출발하는 최단 거리를 구함(출발지만 정함)
  • 음수 사이클 없어야 함(음수 가중치 허용)
  • O(nm) 시간 복잡도 가짐
  • 동적 계획법 사용, relaxation 기법

최단 거리 구하는 알고리즘에서 출발지 하나를 고르는 것은 다익스트라와 같다. 다익스트라와 벨만-포드의 차이점은 아래와 같다.

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

🔎 벨만-포드 알고리즘 과정

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개 만큼 반복하는 과정을 한 번 더 진행한다. 이 때 바뀌는 값이 있다면 음수 사이클이 존재하는 것이다.

💻 벨만-포드 알고리즘 구현 - Java

그래프 구현은 간선을 리스트로 묶어 구현했다.

  • 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

출력 결과
음수 사이클 존재
profile
go_go_
개발도 하고 싶은 클라우드 엔지니어
이전 포스트

[알고리즘/Java]다익스트라(Dijkstra) 알고리즘

다음 포스트

[알고리즘/Java] 플로이드-와샬(Floyd-Warshall) 알고리즘

0개의 댓글