<Algorithm> 53. 11404번 플로이드

1. 11404번 플로이드

• 기본 플로이드 워셜 알고리즘 문제, 3중 for문을 이용하여 처음 반복은 직선이 아닌 거쳐가는 부분을 뜻하며 두 세번째는 직진루트이다.

• 모든 경로에 대한 최단거리를 구할 때 사용한다. 시간복잡도 O(V^3)

• 모든 경로에 대한 우회루트를 계산하여 가장 작은 값을 최단경로로 사용한다

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Main {     public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br =new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  int N = Integer.parseInt(br.readLine())+1;         int M = Integer.parseInt(br.readLine());         int[][] arr = new int[N][N];                          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 w = Integer.parseInt(st.nextToken());                          if(arr[a][b] > w || arr[a][b] == 0) {                 arr[a][b] = w;             }         }                  fyold(arr, N);                  for(int i = 1; i < N ; i ++) {             for(int j = 1; j < N ; j ++) {                     System.out.print(arr[i][j] + " ");             }          System.out.println();         }     }          public static void fyold(int[][] arr, int N) {                  for(int k = 1; k < N; k ++) {             for(int i = 1; i < N; i ++) {                 for(int j = 1; j < N; j ++) {                     if(i == j) continue;                                          if(((arr[i][k] + arr[k][j]) < arr[i][j] )|| arr[i][j] == 0) {                         if(arr[i][k]*arr[k][j] !=0) {                             arr[i][j] = arr[i][k] + arr[k][j];                         }                     }                 }             }         }              }      }   Colored by Color Scripter

cs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static final int INF=999999;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine())+1;
        int M = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][N];
        
        
        for(int i = 0; i < N ; i++) {
            Arrays.fill(arr[i], INF);
        }        
        
        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 w = Integer.parseInt(st.nextToken());
            
            if(arr[a][b] > w || arr[a][b] == INF) {
                arr[a][b] = w;
            }//입력 중 겹치는 부분이 존재할경우
        }
        
        for(int k = 1; k < N; k++) {
            for(int i = 1; i < N ; i++) {
                for(int j = 1; j < N; j++) {
                    if(arr[i][j] > arr[i][k] + arr[k][j] && i!=k && j!=k && i!=j) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }// 경로 선택지 -> 다이렉트 , 경유해서 가는 법 
            }
        }
            for(int i = 1; i < N ; i++) {
                for(int j = 1; j < N; j++) {
                    if(arr[i][j]==INF) {
                        System.out.print(0 +" ");
                    }else {
                        System.out.print(arr[i][j] +" ");
                    }
                 }
                System.out.println();
            }        
        
    }
}