[알고리즘] 플로이드 워셜(Floyd-Warshall)

 목  차

• 플로이드 워셜(Floyd-Warshall)
• 기본 개념과 작동 원리
• 구현하며 배운 것들
• 구현 방법

 
 

---

 

  플로이드 워셜(Floyd-Warshall)

 
최단 경로를 구하는 알고리즘 중에는 대표적으로 다익스트라 알고리즘이 존재한다. 다익스트라 알고리즘의 경우 한 점에서 다른 한 점으로의 최단경로를 구하는 반면에 플로이드 워셜은 모든 정점 사이의 최단경로를 찾는 데에 사용된다. 시간 복잡도는 O(V^3)이다.
 
 
 

---

 

  기본 개념 및 작동 원리

 

  기본 개념

위에서 언급하였듯이 모든 정점의 최단경로를 찾는 알고리즘이다.
 

  작동 원리

기본적으로 동적 프로그래밍을 기반으로 작동을 하지만 복잡하면 굳이 생각하지 않아도 된다. 이 알고리즘에서는.
 
이 알고리즘에서는 각 점을 순회하는데, 시작점으로써가 아닌 '경유점'의 개념으로 접근을 하게 된다. 이게 무슨 뜻일까?
다익스트라에서는 시작점이 있고 끝점이 있다. 우리는 시작점을 정하고 끝점을 정한다. 이 알고리즘에서는 모든 점을 방문하고 방문하는 점들을 '경유'하였을 때의 거리가 더 짧다면 갱신하는 것이다. 코드를 보면 이해하기 쉽다.
 

        for(int i = 1; i <= N; i++){  // 경유노드
            for(int j = 1; j <= N; j++){  // 출발노드
                for(int k = 1; k <= N; k++){. // 도착노드

                    dist[j][k] = Math.min(dist[j][k], dist[j][i] + dist[i][k]);

                }
            }
        }

 
 
i를 경유점으로 하여서 보자, dist[j][i] 로 먼저 가서 dist[i][k] 로 가는 것을 구하는 것이다. (j -> i -> k)
 
첫 번째 for 문: 경유노드
두 번째 for 문: 출발노드
세 번째 for 문: 도착노드
 
 
 

---

 

 구현 코드

 

package src.Graph.Floyd_Warshall;

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

public class 플로이드_11404 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int[][] dist = new int[N + 1][N + 1];

        // 모든 값 2^31 - 1 로 설정
        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= N; j++){
                dist[i][j] = 1000000000;
                if(i == j) dist[i][j] = 0;
            }
        }

        // 초기값 설정
        for(int i = 1; i <= M; i++){
            StringTokenizer bus = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(bus.nextToken());
            int to = Integer.parseInt(bus.nextToken());
            int weight = Integer.parseInt(bus.nextToken());

            dist[from][to] = Math.min(weight, dist[from][to]);
        }

        for(int i = 1; i <= N; i++){  // 중간노드
            for(int j = 1; j <= N; j++){  //
                for(int k = 1; k <= N; k++){

                    dist[j][k] = Math.min(dist[j][k], dist[j][i] + dist[i][k]);

                }
            }
        }

        StringBuilder sb = new StringBuilder();


        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){

                if(dist[i][j] < 1000000000) {
                    sb.append(dist[i][j]).append(" ");
                } else {
                    sb.append(0).append(" ");
                }


            }
            sb.append('\n');
        }

        System.out.println(sb);



    }
}