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

플로이드 워셜

모든 정점에서 다른 정점으로 도달할 수 있는 경우를 하나하나 일일히 따져서 각 정점에서의 최단거리로 도달할 수 있는 경로를 갱신하는 방법으로 각 점에서 갈 수있는 최단거리를 만들 수 있는 알고리즘이다.

• 다익 스트리아는 한 정점을 기준으로 최단거리를 갱신하는 반면 플로이드는 기준이 없고 모든 정점에서의 다른 정점으로 가는 경우의 수를 다 따져서 갈 수 있는 모든 거리를 최소로 만드는 알고리즘의 차이가 있다.

• 다익스트라는 n^2 과 nlogn 의 방식이 있다. 워셜은 이것보다 훨씬 복잡도가 더 큰 n^3을 가지고 있다. 그 대신 모든 정점이다. 즉 1차원 테이블이 아닌 2차원 테이블이다.

해당 한 정점을 기준으로 하여 모든 경우의 수를 다 돌아 짧은거리로 갱신하는 방식이다. 다익스트라에 1차원 테이블의 탐색을 2차원이 경우 n^2이 되는 경우라고 비유하면 된다.

다익스트라는 그리디 알고리즘의 분류로 매 최선의 선택을하여 갱신하는 방법이였다. 하지만 워셜은 해당 모든 경우의 수를 고려하여 갱신하는 부분에서 동적 프로그래밍으로 분류 된다.
해당 점화식은

,

i점에서 j점으로 가는 경로 = 최솟값(i점에서 j점으로 가는 경로 ,i점에서 k로가는 경로+ k에서 j로 가는 경로)

예를 들어 설명하면 입력값이 주어지고 해당 2차원 배열 인접 행렬을 보고 해당 점에서 다른 점으로 도달할 수 없는 입력을 받았지만 2차원 인접행렬을 보고 어떤 정점을 거쳐 갈 수 있는 경로도 찾을 수 있으며 기존에 2->3으로 가는것이 5였는데 2->1->3으로 가는건 2였네? 하면서 더 짧은 거리를 도달할 수 있다.

백준문제에서 주의할 것은 입력값을 자세히 보자.... 정점과 거리가 중복이 되어 입력된 값 중 최단거리만을 저장해야 한다.

package Thur_Sunday_aWeek_Al.Random2;

import java.util.Arrays;
import java.util.Scanner;

public class Floyd {
    static int INF= (int)1e9;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[][] matrix =new int[n+1][n+1];

        for (int i = 1; i < n+1; i++) {
            Arrays.fill(matrix[i],INF);
        }

        for (int i = 0; i < n+1; i++) {
            matrix[i][i]=0;
            matrix[i][0]=0;
        }

        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            if(matrix[a][b]!=INF) { // 이미 들어간 값이라면..
                matrix[a][b]= matrix[a][b] > c ? c : matrix[a][b];
            }
            else
            {
                matrix[a][b]=c;
            }
        }

        //=======================

        // 2 -> 4  2-[1,2,3,4,5]-[1]-1
        for (int k =1; k <n+1 ; k++) {
            for (int i = 1; i < n+1; i++) {
                for (int j = 1; j < n+1; j++) {
                    matrix[i][j]=Math.min(matrix[i][k]+matrix[k][j],matrix[i][j]);
                }
            }
        }
        for (int i = 1; i < n+1; i++) {
            for (int j =1; j < n+1; j++) {
                if(matrix[i][j]==INF)
                    System.out.print(0+" ");
                else
                    System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
    }
}