09. 최단 경로 - 플로이드 위셜 알고리즘

플로이드 위셜 알고리즘이란? '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용

플로이드 위셜 알고리즘은 다익스트라 알고리즘과는 다르게 2차원 리스트에 '최단 거리' 정보를 저장한다는 특징이 있다.
(모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문)
노드의 개수가 N이라고 할 때, N번 만큼의 단계를 반복하여 '점화식에 맞게' 2차원 리스트를 갱신하기 때문에 다이나믹 프로그래밍으로 볼 수 있다.

각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다.
ex) 1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하면 된다.
알고리즘에서는 현재 확인하고 있는 노드를 제외하고, N-1 개의 노드 중에서 서로 다른 노드 (A, B) 쌍을 선택한다.
이후에 A -> 1번 노드 -> B로 가는 비용을 확인한 뒤에 최단 거리를 갱신한다.

구체적인 (K번의 단계에 대한) 점화식은 다음과 같다.

따라서 전체적으로 3중 반복문을 이용하여 이 점화식에 따라 최단 거리 테이블을 갱신하면 된다.
('A에서 B로 가는 최소 비용' 과 'A에서 K를 거쳐 B로 가는 비용'을 비교하여 더 작은 값으로 갱신)
즉, '바로 이동하는 거리'가 '특정한 노드를 거쳐서 이동하는 거리'보다 더 많은 비용을 가진다면 이를 더 짧은 것으로 갱신

시간 복잡도 : O(N^3)

(노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려)

 

플로이드 위셜 알고리즘 소스 코드

package graph;

import java.util.*;

public class graph03 {

    public static final int INF = (int) 1e9; // 무한을 의미하는 값 설정(연결되지 않은 간선)
    public static int n, m; // 노드의 개수(n), 간선의 개수(m)
    public static int[][] graph = new int[501][501];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        for(int i=0; i<501; i++){
            Arrays.fill(graph[i], INF); // 최단 거리 테이블 모두 무한으로 초기화
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j) graph[i][j] = 0; // 자기 자신으로 가는 비용 0으로 초기화
            }
        }

        for(int i=0; i<m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph[a][b] = c;
        }

        // 점화식에 따라 플로이드 위셜 알고리즘 수행
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                for(int k=1; k<=n; k++){
                    graph[j][k] = Math.min(graph[j][k], graph[j][i]+graph[i][k]);
                }
            }
        }

        // 수행된 결과를 출력
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(graph[i][j] == INF) System.out.print("INFINITY ");
                else System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
    }
}

 

📚 실전문제

방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하려 한다. 공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 이 때, 다른회사로 이동하기 위한 시간은 정확히 1만큼의 시간이 소요된다.

또한 오늘 A씨는 소개팅에도 참여해야 한다. 소개팅의 상대는 K번 회사에 존재한다. 방문 판매원 A는 X번 회사에 물건을 팔러 가기 이전에 소개팅 상대의 회사에 가서 함께 커피를 마실 예정이다. 따라서 A씨는 1번 회사에서 출발해 K번 회사를 거쳐 X번 회사로 가는 것이 목표다. 이 때 A씨는 가장 빠르게 이동하려고 한다. A씨가 이동하게 되는 최소 시간을 계산하는 프로그램을 작성해라. 이 때 소개팅의 상대방과 커피를 마시는 시간 등은 고려하지 않는다.

예를 들어 N=5, X=4, K=5이고 회사 간 도로가 7개면서 각 도로가 다음과 같이 연결되어 있을 때를 가정할 수 있다.

(1번, 2번), (1번, 3번), (1번, 4번), (2번, 4번), (3번, 4번), (3번, 5번), (4번,5번)

이때 방문 판매원 A가 최종적으로 4번 회사에 가는 경로를 (1 - 3 - 5 -4)로 설정하면, 소개팅에도 참석할 수 있으면서 총 3만큼의 시간을 이동할 수 있다.
따라서 이 경우 최소 이동 시간은 3이다.

 

📝 문제 해설

1번 노드에서 X(소개팅)를 거쳐 K(방문판매 회사)로 가는 최단 거리 = 1번 노드에서 X까지의 최단 거리 + X에서 K까지의 최단 거리

 

💻 코드 

package graph;

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

public class graph04 {
    public static final int INF = (int) 1e9;
    public static int n, m, x, k;
    public static int[][] graph = new int[101][101];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        for(int i=0; i<101; i++){
            Arrays.fill(graph[i], INF); // 최단 거리 테이블 모두 무한으로 초기화
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j) graph[i][j] = 0; // 자기 자신으로 가는 비용 0으로 초기화
            }
        }

        for(int i=0; i<m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        x = sc.nextInt(); // 방문해야하는 회사 위치
        k = sc.nextInt(); // 소개팅 참석 회사 위치

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                for(int k=1; k<=n; k++){
                    graph[j][k] = Math.min(graph[j][k], graph[j][i]+graph[i][k]);
                }
            }
        }

        int distance = graph[1][k] + graph[k][x];

        if(distance >= INF) System.out.println(-1);
        else System.out.println(distance);
    }
}