최단 경로 알고리즘(벨만-포드)

벨만-포드

• 음수 간선이 포함되어 있어도 최단 경로 구할 수 있음
• 음수 사이클이 있으면 정상적으로 동작하지 않음
• 매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느림
• 알고리즘 복잡도: O(VE)

백준11657

풀이 방법

1. 그래프 구축

   • 각 도시와 도시 간의 버스 정보로 그래프를 구성

2. 벨만-포드 알고리즘 적용

   • 음수 사이클이 존재하면 감지

3. 결과

   • 각 도시로 가는 최단 경로를 출력하며, 경로가 존재하지 않으면 -1을 출력
   • 음수 사이클이 존재할 경우 -1을 출력

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

public class Main {
    static class Edge {
        int from, to, weight;

        Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    static final long INF = Long.MAX_VALUE;
    static List<Edge> edges;
    static long[] dist;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        edges = new ArrayList<>();
        dist = new long[N + 1];
        Arrays.fill(dist, INF);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            edges.add(new Edge(from, to, weight));
        }

        if (bellmanFord(1)) {
            System.out.println("-1");
        } else {
            StringBuilder sb = new StringBuilder();
            for (int i = 2; i <= N; i++) {
                sb.append(dist[i] == INF ? "-1" : dist[i]).append("\n");
            }
            System.out.print(sb);
        }
    }

    static boolean bellmanFord(int start) {
        dist[start] = 0;

        for (int i = 1; i < N; i++) {
            for (Edge edge : edges) {
                if (dist[edge.from] != INF && dist[edge.to] > dist[edge.from] + edge.weight) {
                    dist[edge.to] = dist[edge.from] + edge.weight;
                }
            }
        }

        for (Edge edge : edges) {
            if (dist[edge.from] != INF && dist[edge.to] > dist[edge.from] + edge.weight) {
                return true; 
            }
        }

        return false; 
    }
}