플로이드 와샬

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

11404번: 플로이드

#특징

1. DP를 통해서 최소거리를 갱신.

2. 모든 정점에서의 최단 경로를 알 수 있음.

3. 시간복잡도 O(N^3)

  for문이 3개가 돌아(k,i,j)

 

#다익스트라랑 vs 플로이드

- 다익스트라

  시간 복잡도 O(N^2), 우선순위큐 사용시 O(ELogV)

  한 정점에서의 최단 경로를 가져옴.

 

- 플로이드

  다익스트라가 O(N^2)이니, N(모든정점)*O(N^2) -> O(N^3)

  모든 정점에서의 최단 경로를 제공하기 때문에 느림...

#소스

package main.java.Temp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class bac11404_플로이드_G4_dp {

    static int N;
    static int M;
    static long dis[][];

	//충분의 큰수..
    //여기선 경로가 없음을 뜻함.
    static final long m = 100000000;

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

        dis = new long[N+1][N+1];

        for(long row[] : dis) Arrays.fill(row, m);
        for(int i =0; i<=N; i++) dis[i][i] = 0;

		//입력
        for(int i =0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());
			
            //위의 문제는 A에서 B로 갈때도 여러 경로가 있어서 최소값을 구함
            if(dis[a][b] != 0) dis[a][b]= Math.min(c,dis[a][b]);
            else dis[a][b] = c;
        }

		//3중 포문, 시간 복잡도 O(n^3)
        for(int k=1; k<=N; k++){
            for(int i=1; i<=N; i++){
                if(k==i) continue;
                for(int j=1; j<=N; j++){
                    if(j == i || k == j) continue;
                    if(dis[i][k] != m && dis[k][j] != m)
                        dis[i][j] = Math.min(dis[i][k] + dis[k][j], dis[i][j]);//경유하면 더가까운지 아닌지
                }
            }
        }

		//m, 즉 충분이 큰값은 경로상 갈수 없음을 뜻하기 때문에, 0으로
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++){
                if(dis[i][j] >= m) System.out.print(0 + " ");
                else System.out.print((dis[i][j]) +" ");
            }
            System.out.println();
        }
    }
}