최단 경로 알고리즘(플로이드-워셜)

플로이드-워셜

• 모든 노드 간의 최단 경로를 구하는 알고리즘
• 음의 간선이 포함되어 있어도 사용 가능
  • 음수 사이클이 있으면 정상 동작하지 않음
• 알고리즘 복잡도(V^3)
  

백준 1956

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

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

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int INF = Integer.MAX_VALUE;

        int[][] dist = new int[V+1][V+1];
        for(int i=0; i<=V; i++){
            Arrays.fill(dist[i], INF);
        }

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int add = Integer.parseInt(st.nextToken());
            dist[start][end] = add;
        }

        for(int middle=1; middle<=V; middle++){
            for(int start=1; start<=V; start++){
                for(int end=1; end<=V; end++){
                    if(dist[start][middle] != INF && dist[middle][end] != INF &&
                            dist[start][end] > dist[start][middle] + dist[middle][end]){
                        dist[start][end] = dist[start][middle] + dist[middle][end];
                    }
                }
            }
        }

        //싸이클
        int result = INF;
        for(int i=1; i<=V; i++){
            if(dist[i][i] < result){
                result = dist[i][i];
            }
        }

        if(result == INF){
            System.out.println(-1);
        }else{
            System.out.println(result);
        }
    }
}