벨만-포드 알고리즘 with 백준 11657번: 타임머신 (Java)

https://www.acmicpc.net/problem/11657

11657번: 타임머신

 

 

 

 

 

 

 

 

---

개념

최단 경로 알고리즘 중 다익스트라는 음의 가중치를 갖는 간선, 플로이드는 음의 사이클을 가지면 제대로 된 답을 내지 않을 수 습니다. 구체적으로, 다익스트라는 '음의 가중치를 갖는 간선이 있을 경우 현재 갈 수 있는 정점 중에서 가장 가까운 정점까지의 거리를 확정지을 수 없기'에,

1) 음의 사이클이 있을 경우 무한 루프가 발생하며

2) 음의 사이클이 없는 경우, 정답은 정확하게 나오나 특정 input에 대해 입력값의 크기의 지수에 비례하는 시간 복잡도를 가질 수 있습니다. (설명: 링크의 댓글)

 

벨만-포드 알고리즘은 간단하게

1) dist를 INF로 초기화. 시작점(source)의 dist[source]는 0으로 초기화하기

2) 모든 간선에 대해 V-1번 for문을 돌아 짧은 경로를 찾기 - 음수 사이클이 없다면 V-1번 내로 모든 점의 최단거리가 확정지어집니다.

3) 간선에 대해 for문을 한 번 더 돌아, 만약 거리가 줄어드는 구간이 있다면 사이클이 있다는 뜻이므로 사이클 검출 후 종료, 아닐 경우 모든 점에 대해 최단 경로의 길이를 찾을 수 있음.

으로 설명할 수 있습니다. 즉, 음의 사이클이 있을 경우 이를 검출할 수 있으며, 음의 사이클이 없는 경우 최단 경로를 구합니다.

간선의 개수 E에 대해 for문을 V번 돌기에, 시간복잡도는 O(VE)입니다.

 

구현은 위키피디아에 있는 psuedocode를 보고 하는 것이 좋아보입니다.

수도코드에 대한 첨언을 하자면,

1) 수도코드에는 음의 사이클을 찾는 과정이 있으니 필요하면 구현하면 됩니다.

2) distance[u] + w < distance[v]를 비교하는 과정에서 distance[u], distance[v]가 inf일 경우, w가 음수라면 값이 갱신됩니다. 하지만 여기서 inf는 수학적인 개념으로, inf + 양수 == inf의 의미로 작성한 거기에, inf 값에 대해서는 따로 처리를 해야합니다.

 

 

 

풀이

* 유의할 점: N = 500, M = 6000, (모든 간선의 시간) = -10000 이고, N번동안 M번의 음의 간선을 모두 갱신하는 경우를 생각해보면 값이 500 * 6000 * -10000 = -300억까지 갈 수 있습니다. 따라서 거리는 long으로 저장해야 합니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static final int INF = 1_000_000_007;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Edge[] edges = new Edge[M];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(A, B, C);
        }
        BellmanFord(1, N, edges);
    }
 
    static void BellmanFord(int source, int V, Edge[] edges) {
        long[] dist = new long[V+1];
        Arrays.fill(dist, INF);
        dist[source] = 0;
        
        for (int i = 0; i < V-1; i++) {
            for (Edge e: edges) {
                int from = e.from;
                int to = e.to;
                long d = e.dist;
                if (dist[from] != INF && dist[from] + d < dist[to]) {
                    dist[to] = dist[from] + d;
                }
            }
        }
        
        for (Edge e: edges) {
            int from = e.from;
            int to = e.to;
            long d = e.dist;
            if (dist[from] != INF && dist[from] + d < dist[to]) {
                System.out.println(-1);
                return;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= V; i++) {
            sb.append((dist[i] == INF)? -1+"\n": dist[i]+"\n");
        }
        System.out.println(sb.toString());
    }
    
    static class Edge implements Comparable<Edge> {
        int from;
        int to;
        long dist;
 
        public Edge(int from, int to, long dist) {
            this.from = from;
            this.to = to;
            this.dist = dist;
        }
 
        public int compareTo(Edge o) {
            return Long.compare(this.dist, o.dist);
        }
    }
}