bellmanFord 알고리즘

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

1. 개요

단일 시작점 최단 경로 알고리즘 (one - to - all)

다익스트라(Dijkstra)와 달리 음수 가중치 간선이 있어도 동작 가능

시간 복잡도: O(V·E) (정점 V, 간선 E)

2. 동작 원리

시작 정점 s에서 거리를 초기화

dist[s] = 0, 나머지 정점은 INF

모든 간선에 대해 V-1번 반복하여 완화(Relaxation)

완화: 더 짧은 경로를 발견하면 거리 갱신

if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;

한 번 더 모든 간선을 검사해서 갱신이 가능하다면

→ 음수 사이클 존재

3. 응용

k번째 반복 후 dist[v]는 시작점에서 v까지 간선 최대 k개를 사용하는 최단 거리를 의미
따라서 V-1번 반복하면 모든 단순 경로를 고려한 최단 거리를 보장

4. 음수 사이클 검출

최단 경로는 간선이 최대 V-1개

그 이후에도 갱신이 발생한다면, 사이클을 포함하는 경로가 더 짧아졌다는 뜻

이는 곧 음수 사이클 존재를 의미

5. code

    public class Main {

	static BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;

	static class Edge {
		int u;
		int v;
		int cost;

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

	static int N, M;

	static long[] dis;

	static List<Edge> graph = new ArrayList<>();

	public static void main(String[] args) throws IOException {

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			graph.add(new Edge(u, v, cost));
		}

		if(!bellmanFord(1)){
			System.out.println(-1);
			System.exit(0);
		}

		for (int i = 2; i <= N; i++) {
			sb.append(dis[i] == Long.MAX_VALUE ? -1 : dis[i]).append("\n");
		}

		System.out.println(sb.toString());
	}

	private static boolean bellmanFord(int start) {
		dis = new long[N + 1];
		Arrays.fill(dis, Long.MAX_VALUE);
		dis[start] = 0;

		for (int i = 1; i <= N - 1; i++) {
			for (Edge edge : graph) {
				if (dis[edge.u] != Long.MAX_VALUE && dis[edge.v] > dis[edge.u] + edge.cost) {
					dis[edge.v] = dis[edge.u] + edge.cost;
				}
			}
		}

		for (Edge edge : graph) {
			if (dis[edge.u] != Long.MAX_VALUE && dis[edge.v] > dis[edge.u] + edge.cost) {
				return false;
			}
		}

		return true;
	}
}

SPFA 알고리즘

1. 개요

벨만–포드 알고리즘 최적화 버전

핵심 아이디어: 거리 배열이 실제로 갱신된 정점만 다시 탐색

일반적으로 다익스트라보다 느리지만, 음수 간선이 있는 경우에 자주 활용됨

2. 동작 원리

시작 정점 s에서 dist[s]=0으로 초기화하고 큐(queue)에 삽입

큐에서 정점을 꺼내 그 정점에 연결된 간선을 확인

더 짧은 경로를 찾으면 dist[v]를 갱신하고, 정점 v를 큐에 넣음

단, v가 이미 큐에 있으면 중복 삽입하지 않음

큐가 빌 때까지 반복

즉, 불필요한 완화를 줄이고, 필요한 정점만 다시 확인하는 방식.

3. 시간 복잡도

최악: O(V·E) (벨만–포드와 동일)

평균: O(E)에 가까운 성능을 보이는 경우도 많음

따라서 실전에서는 평균적으로 매우 빠르지만, 최악 성능 보장이 없는 알고리즘

4. 음수 사이클 검출

어떤 정점이 V번 이상 큐에 들어가면 음수 사이클이 존재한다고 판별할 수 있다.
(최단 경로가 무한히 줄어드는 현상)

code

import java.io.*;
import java.util.*;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;

	static class Edge {
		int v;
		int cost;

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

	static int N, M;
	static long[] dis;
	static boolean[] inQueue;
	static int[] count;
	static List<Edge>[] graph;

	public static void main(String[] args) throws IOException {

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		graph = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			graph[u].add(new Edge(v, cost));
		}

		if (!SPFA(1)) {
			System.out.println(-1);
			System.exit(0);
		}

		for (int i = 2; i <= N; i++) {
			sb.append(dis[i] == Long.MAX_VALUE ? -1 : dis[i]).append("\n");
		}

		System.out.println(sb.toString());
	}

	private static boolean SPFA(int start) {
		dis = new long[N + 1];
		Arrays.fill(dis, Long.MAX_VALUE);
		inQueue = new boolean[N + 1];
		count = new int[N + 1];

		Queue<Integer> q = new LinkedList<>();
		dis[start] = 0;
		q.add(start);
		inQueue[start] = true;
		count[start]++;

		while (!q.isEmpty()) {
			int u = q.poll();
			inQueue[u] = false;

			for (Edge e : graph[u]) {
				if (dis[u] != Long.MAX_VALUE && dis[e.v] > dis[u] + e.cost) {
					dis[e.v] = dis[u] + e.cost;
					if (!inQueue[e.v]) {
						q.add(e.v);
						inQueue[e.v] = true;
						count[e.v]++;
						if (count[e.v] >= N) {
							return false; // 음수 사이클 존재
						}
					}
				}
			}
		}

		return true;
	}
}

백준 11657 타임머신
https://www.acmicpc.net/problem/11657