[Algorithm] 플로이드-워셜 알고리즘

플로이드-워셜 알고리즘은 모든 최단 경로를 구하는 알고리즘이다.
또한 알고리즘은 한 번 실행하면 모든 노드 간의 최단 경로를 구할 수 있다. 벨만 포드와 같이 음의 가중치를 허용한다. 그리고 모든 노드 간의 최단 거리를 구해야하므로 2차원 인접행렬을 구성한다.

플로이드-워셜 알고리즘 (floyd-warshall) 특징

모든 정점에서 모든 정점까지의 최단거리를 구한다. 음수 가중치는 허용하지만, 음수 사이클은 없어야 한다. 그래프 비용 인접행렬로 표현되어 있다고 가정한다. 동적 계획법을 이용하며 시간복잡도는 O(V^3)이다.

이 외에도 동작원리가 궁금하다면 최단 경로 알고리즘 “최단 경로 알고리즘 정리”을 정리해둔 글로 가면 자세한 동작 원리를 확인해 볼 수 있다.

구현 방법

동작 과정

경유지 k, 출발 정점 i, 도착 정점을 j 라고 하고, 그래프는 graph라는 이중 배열에 저장되어 있다. graph[i][j]는 i번 노드에서 j번 노드까지 가는 최단 거리이다.
만약, graph[i][k]+graph[k][j]면 i부터 j까지 가는 최단거리이다.
graph[i][j]>graph[i][k] + graph[k][j]이면 i부터 j까지 가는데 k를 거쳐서 가는 것이 더 최단거리이다. 따라서 graph[i][j]는 graph[i][k]+graph[k][j]로 갱신해준다.

graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

2차원 배열을 선언하고 배열의 값을 전부 INF로 초기화 한다. ( 출발노드 i,도착노드 j 가중치 w ) i==j일 경우는 자기 자신에게 가는데 걸리는 최단 경로 값을 의미하기 때문에 0으로 갱신해준다.
최단 거리 배열에 그래프 데이터를 저장한다. graph[i][j] = w 로 에지의 정보를 배열에 입력한다. 플로이드-워셜 알고리즘은 그래프를 인접행렬로 표현한다는 것을 알 수 있다.

점화식으로 배열을 업데이트 한다.
위의 플로이드 워셜 점화식을 3중 for문 형태로 반복하면서 배열의 최단 경로를 갱신한다.

  
for 경유지 K에 관해 ( 1~N ) //이때 N:노드 개수를 의미한다.
 for 출발 노드 i에 대해
     for 도착 노드 j에 관해
     graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

소스코드

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

public class Floyd {
    static final int INF = 10000001;
    static int N;
    static int M;
    static int[][] graph;
    public static void floyd(){
        //경유지에 관해
        for(int k=1;k<=N;k++){
            //출발지에 관해
            for(int i=1;i<=N;i++){
                //도착지에 관해
                for(int j=1;j<=N;j++){
                    graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
                }
            }
        }
        //출력
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(graph[i][j]==INF) System.out.print("INF"+" ");
                else System.out.print(graph[i][j]+" ");
            }
            System.out.println();
        }



    }
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        System.out.print("정점의 개수, 간선의 개수 입력 >>");
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        //1. 배열 선언 후 초기화
        graph = new int[N+1][N+1];

        for(int i=0;i<N+1;i++){
            for(int j=0;j<N+1;j++){
                if(i==j) continue;
                graph[i][j] = INF;
            }
        }
        //2. 최단 거리 배열에 그래프 데이터 저장하기
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph[start][end] = w;
        }
        floyd();
    }
}

floyd()메소드에서는 플로이드 점화식을 3중 for문으로만 구현해 주면 된다. 만약 start정점에서 end 정점까지 최단 경로를 구하고 싶다면, floyd 메소드가 실행되고 난 뒤, graph[start][end]를 이용해 출력하면 된다.

Reference

Do it! 알고리즘 코딩 테스트 자바 편 (김종관 저, 이지스퍼블리싱)

[Algorithm] 플로이드-워셜 알고리즘