[APS응용] 그래프최소비용3 : 벨만-포드, 플로이드워셜

[알고리즘개념]

[APS응용] 그래프최소비용3 : 벨만-포드, 플로이드워셜

whatezlife 2025. 3. 31. 15:39

1. 벨만 포드 알고리즘

단일 출발점 최단 경로 문제를 해결 가능 (음의 가중치를 포함하는 그래프에서 최단 경로 구할 수 있음)

음수 사이클(negative cycle) 탐지 가능 -> 최단 경로가 '무한대로 줄어드는 경우' 방지
모든 간선을 순회하면서 알려진 최단 경로보다 더 짧은 경로가 있다면 값을 갱신하는 과정을 진행 (최대 V-1번)
시간 복잡도 O(VE) // V:정점의 수, E:간선의 수
동작 과정
- 초기화 -> 시작 정점 거리 0. 다른 모든 정점 거리 무한대
- Relaxation 과정(V-1번 반복) -> 모든 간선 갱신 (업데이트)
- 음수 사이클 검사
  - 최단 거리 갱신 O -> 음의 사이클 존재 O
  - 최단 거리 갱신 X -> 음의 사이클 존재 X;

[초기화]
모든 거리 = INF
시작 정점의 거리만 0으로 설정

     ↓

[V-1번 반복]
모든 간선(u → v, cost) 확인:
    if (dist[u] + cost < dist[v]):
        dist[v] = dist[u] + cost

     ↓

[음수 사이클 체크]
한 번 더 전체 간선 확인:
    if (dist[u] + cost < dist[v]):
        → 음수 사이클 존재!

📊 벨만포드 동작 예시 (표 형태)

예시 그래프

시작 정점: A

간선 목록:
A → B (4), A → C (2), C → B (-1), B → D (2), C → D (4)

단계거리	A	B	C	D	비고
초기	0	∞	∞	∞	시작 정점만 0
1회차	0	4	2	6	A→B, A→C, C→B, B→D, C→D 갱신
2회차	0	1	2	3	C→B(-1) 다시 갱신됨
3회차	0	1	2	3	더 이상 갱신 없음

총 V-1 = 3번 반복 후 거리 고정
4번째 반복 시 변화 없으면 → 음수 사이클 없음

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class 그래프최소비용06_벨만포드 {
	static class Edge{
		int s, e, cost;
		public Edge() {
		}
		public Edge(int s, int e, int cost) {
			super();
			this.s = s;
			this.e = e;
			this.cost = cost;
		}
	}
	static String input1 = "6 7\r\n"
			+ "0 1 4\r\n"
			+ "0 2 5\r\n"
			+ "1 3 -2\r\n"
			+ "2 4 8\r\n"
			+ "3 5 7\r\n"
			+ "4 2 -3\r\n"
			+ "4 5 6";
	
	static String input2 = "4 4\r\n"
			+ "0 1 5\r\n"
			+ "1 2 -8\r\n"
			+ "2 1 3\r\n"
			+ "2 3 6";
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(input1);
		int V = sc.nextInt();
		int E = sc.nextInt();
		List<Edge> edges = new ArrayList<>();
		for (int i = 0; i<E; i++) {
			int s= sc.nextInt();
			int e = sc.nextInt();
			int cost = sc.nextInt();
			edges.add(new Edge(s, e, cost));
		}//간선을 입력받자
		dist = new int[V]; // 시작 정점은 0번부터..
		bellmanFord(V, 0, edges); 

	}
	static int[] dist;
	static final int INF = Integer.MAX_VALUE;

	// V: 전체 정점의 개수
	// start : 시작 정점
	// edges : 간선의 배열
	private static void bellmanFord(int V, int start, List<Edge> edges) {
		Arrays.fill(dist, INF);
		dist[start] = 0; // 시작점만 0으로 바꾼다
		//1. 모든 간선을 (v-1)번 반복 => relazation 작업 수행
		for (int i = 0; i<V-1; i++) {
			boolean flag = false;
			for(Edge edge : edges) {
				//갱신 : 출발점이 무한대가 아닌 애들만!
				if (dist[edge.s]!=INF && dist[edge.s]+edge.cost < dist[edge.e]) {
					dist[edge.e] = dist[edge.s]+edge.cost; //갱신!
					flag = true;
				}
			}
			if(!flag) break; // 조기 종료 하겠다 . 갱신이 일어나지 않았어.
		}// 완화작업 끝
		//2. 음수 사이클 쳌
		boolean negativeCycle = false;
		for (Edge edge : edges) {
			if (dist[edge.s] != INF && dist[edge.s]+edge.cost < dist[edge.e]) {
				//해당 조건문이 만족한다.... -> 갱신이 일어났다! (음의 사이클이 존재한당)
				negativeCycle = true;
			}
		}
		//3. 결과 확인
		if (negativeCycle) System.out.println(" 음의 사이클");
		else System.out.println(Arrays.toString(dist));
	}

}

2. 플로이드 워셜 알고리즘

모든 정점 쌍에 대한 최단 경로 -> 단일 출발점 X, 모든 정점 쌍에 대한 최단 경로 계산

음의 가중치를 포함하는 그래프에서 최단 경로 구할 수 있음 (단 음의 사이클 X)
경유지를 하나씩 추가하면서, 각 정점 쌍의 경로를 점진적으로 개선함
경로는 모름, 오로지 arr에는 거리만 존재함
시간복잡도 O(v^3) // V : 정점의 수
동작 과정 (경 출과 도둑) -> 경유지 출발 도착
- 초기화 : 직접 연결된 간선이 있으면 해당 가중치로 갱신, 간선이 없는 경우 무한대, 자기 자신은 0
- 중간 정점 (경유지) 추가 (3중 for문) : 중간 정점 K를 경유지로 사용했을 때 i에서 j로 가는 경로 거리 갱신
- 음수 사이클 검사 : 어떤 정점 i에 대해 d[i][i] <0인 경우가 발생하면 음수 사이클 존재

📊 플로이드 워셜 동작 예시 (표 형태)

정점: A, B, C
간선 목록:

A → B (4)
A → C (2)
C → B (1)

💡 시작 정점 개념 없이 모든 정점 쌍에 대한 최단 거리를 구함

⏱ 초기 거리 행렬 (D₀)

ABC

A	0	4	2
B	∞	0	∞
C	∞	1	0

간선 없는 곳은 ∞ (무한), 자기 자신은 0

🔁 1단계: 경유지 A 사용 (k = A)

ABC비고

A	0	4	2	그대로
B	∞	0	∞	변화 없음
C	∞	1	0	변화 없음

🔁 2단계: 경유지 B 사용 (k = B)

ABC비고

A	0	4	2	그대로
B	∞	0	∞	그대로
C	∞	1	0	그대로

변화 없음

🔁 3단계: 경유지 C 사용 (k = C)

ABC비고

A	0	3	2	A → C → B = 2 + 1 = 3 으로 갱신됨
B	∞	0	∞	변화 없음
C	∞	1	0	그대로

✅ 최종 거리 행렬

ABC

A	0	3	2
B	∞	0	∞
C	∞	1	0

🔍 음수 사이클 검사

d[i][i] < 0인 정점이 없음 → 음수 사이클 없음

import java.util.Scanner;

public class 그래프최소비용07_플로이드워셜 {
	static String input1 = "5 9\r\n"
			+ "0 1 3\r\n"
			+ "0 2 8\r\n"
			+ "0 4 -4\r\n"
			+ "1 3 1\r\n"
			+ "1 4 7\r\n"
			+ "2 1 4\r\n"
			+ "3 0 2\r\n"
			+ "3 2 -5\r\n"
			+ "4 3 6\r\n"
			+ "\r\n";
	static String input2 = "4 5\r\n"
			+ "0 1 1\r\n"
			+ "0 3 4\r\n"
			+ "1 2 1\r\n"
			+ "2 0 -3\r\n"
			+ "3 2 2";
	static final int INF = Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc = new Scanner(input1);
		int V = sc.nextInt(); //정점의 개수 (시작 정점의 번호 확인)
		int E = sc.nextInt(); //간선의 개수
		int[][] dist = new int[V][V]; //0번부터 하더라..
		//i==j 어차피 0이야
		for (int i = 0; i<V; i++) {
			for (int j = 0; j<V; j++) {
				if(i!=j) dist[i][j] = INF; // dist 다시 호출 안 할꺼면 이렇게 해두 돼
			}
		}//dist 초기값 설정
		for (int i = 0; i<E; i++) {
			int s = sc.nextInt();
			int e = sc.nextInt();
			int cost = sc.nextInt();
			dist[s][e] = cost; //무향이면 반대로도 해야하지만 지금은 유향이니깐
		}
		//플로이드 워셜
		for (int k = 0; k<V; k++) {
			for (int i = 0; i<V; i++) {
				if (dist[i][k]==INF) continue; //i의 출발지에서 경유지 k까지 거리가 무한대!
				for (int j = 0; j<V; j++) {
					if (dist[k][j]==INF) continue; //경유지 k로부터 도착지 j까지 무한대라면 할 필요 없음
					dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
				}//도착점
			}//출발점
		}//경유지
		
		//옵션)음수사이클 검사
		boolean negativeCycle = false;
		for (int i = 0; i<V; i++) {
			if (dist[i][i]<0) {
				negativeCycle = true;
				break;
			}
		}
		if (negativeCycle) System.out.println("음의 사이클 존재");
		else {
			for (int i = 0; i<V; i++) {
				for (int j = 0; j<V; j++) {
					System.out.printf("%4d",dist[i][j]);
				}
				System.out.println();
			}
		}
		
	}

}

📊 3. 최단 경로 알고리즘 비교 분석

구분	다익스트라(Dijkstra)	벨만-포드 (Bellman-Ford)	플로이드-워셜 (Floyd-Warshall)
문제 유형	단일 출발점 최단 경로	단일 출발점 최단 경로	모든 정점 쌍 최단 경로
음수 가중치	허용 ❌	허용 (음수 사이클은 X)	허용 (음수 사이클은 X)
음수 사이클	검출 ❌	검출 가능	검출 가능
시간 복잡도	O(E log V)	O(VE)	O(V³)
장점	음수가 없을 경우 빠름	음수 가중치 처리 가능	모든 정점 쌍의 최단 경로 계산 가능
단점	음수 가중치 처리 불가	다익스트라보다 느림	정점 수가 많을 경우 비효율적