벨만-포드 알고리즘

thsamajiki·2022년 10월 25일
0

알고리즘

목록 보기
6/8

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

  • 그래프 최단 경로 구하는 알고리즘
  • 하나의 정점에서 출발하는 최단 거리를 구함(출발지만 정함)
  • 음수 사이클 없어야 함(음수 가중치 허용)
  • 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로 하겠다.

https://velog.velcdn.com/images/suk13574/post/8caeb976-af35-4933-a433-171cabc04479/image.PNG

1) n = 1

https://velog.velcdn.com/images/suk13574/post/e6bfb72c-f518-408d-98de-90861eaa7fc3/image.PNG

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

https://velog.velcdn.com/images/suk13574/post/1d56bf42-9c59-496a-8091-5ba8f9805c51/image.PNG

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

https://velog.velcdn.com/images/suk13574/post/379d7381-e9ab-405f-be3d-ae13256e97c4/image.PNG

dist의 배열에 무한인 값이 없으므로 모든 간선을 위의 방식대로 살펴본다. n = 5까지 반복한다.

최종 모습)

https://velog.velcdn.com/images/suk13574/post/ef039335-3d30-4acb-8de0-0516b709aea6/image.PNG

음수 사이클 확인하기

https://velog.velcdn.com/images/suk13574/post/def21af6-eb44-4a40-bcdf-af5a17571212/image.PNG

위 그림처럼 음수 가중치가 포함된 사이클이 있으면 음수 사이클이 존재하는 것이다. 벨만-포드 알고리즘에서 정점 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
thsamajiki
안드로이드 개발자
이전 포스트

다익스트라 알고리즘

다음 포스트

플로이드-와샬 알고리즘

0개의 댓글