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

플로이드-워셜(Floyd-Warchall) 알고리즘

가중 그래프에서 모든 노드 쌍들에 대한 최단 경로를 구할 때 사용하는 알고리즘이다.

가중치가 음/양수일 때 모두 사용 가능하다.

 

알고리즘 동작

• 모든 vertex쌍 간의 최단 경로를 갱신하여야 하므로 인접 행렬을 사용한다.
• 정점 A에서 B로 가는 경로에서 거칠 수 있는 모든 노드(K)을 확인하여 해당 노드(K)를 경유할 경우 경로 길이가 더 짧아진다면 그 값을 테이블에 갱신한다. (D[i,j] = min( D[i,j] , D[i,k]+D[k,j])
  
  • 3중 for문을 사용한다. (D[i,k]와 D[k,j] 에서 공통인 중간점 k를 가장 바깥 for문으로 둔다.)
• 만일 dist[i][i] < 0 이 되는 노드 i가 존재한다면, 이는 i에서 i로 돌아오는 경로 중에 음수 사이클이 존재한다는 의미로, 최단 거리 테이블을 확정할 수 없다.

구현 방법

1. 인접행렬 dist를 초기화
   1. dist[i][j]에 노드 i에서 j로 가는 초기 비용 저장
   2. dist[i][i] = 0
   3. 연결되지 않은 경우 INF로 저장
2. 모든 노드(i,j) 사이의 경로를 확인
   1. 두 노드 사이에서 경유할 수 있는 모든 경유 노드(k)를 확인
   2. 노드 k를 거쳐갈 경우의 경로 길이를 확인한 뒤, 더 짧다면 해당 길이로 갱신 (dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
3. dist[i][i] < 0인 노드 확인, 있다면 음수 사이클 존재

예시 문제 & 구현 코드

 

모든 정점 쌍에 대한 최단 거리를 구하는 문제이다.

 

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

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 n = Integer.parseInt(st.nextToken()); // 도시의 개수
    
        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken()); // 버스의 개수
    
        int[][] dist = new int[n + 1][n + 1];
        for(int i = 1 ; i <= n ; i ++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
            dist[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()); // 도착
            int c = Integer.parseInt(st.nextToken()); // 비용
    
            if(dist[a][b] > c) {
                dist[a][b] = c;
            }
        }
    
        // k: 중간점, i: 시작점, j: 끝점
        for(int k = 1 ; k <= n ; k++) {
            for(int i = 1 ; i <= n ; i++) {
                if(dist[i][k] == Integer.MAX_VALUE) continue; // 시작점에서 중간점까지의 경로가 없음
                for(int j = 1 ; j <= n ; j++) {
                    if(dist[k][j] == Integer.MAX_VALUE) continue; // 중간점에서 끝점까지의 경로가 없음
    
                    if(dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= n ; j++) {
                if(dist[i][j] == Integer.MAX_VALUE) {
                    System.out.print(0 + " ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}