Floyd-Warshall (플로이드 워셜)

V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 모든 정점 사이의 최단경로를 구하는 알고리즘으로 (모든 노드 간에 최단거리를 구하는 알고리즘) 음수 사이클이 없는 그래프 내의 각 모든 정점에서 각 모든 정점에 까지의 최단거리를 구하는데 사용된다. 음수인 가중치를 갖는 간선이 존재해도 된다. 

 

어떤 두 정점 사이의 최단 경로는 어떤 경유지(K)를 거치거나 거치지 않는 경로 중 하나이다. 

ex). 정점 A와 정점 B 사이의 최단 경로 = A-B 또는 A-K-B

 

만약, 경유지를 거친다면 최단 경로를 이루는 부분 경로 또한 최단 경로이다. 

ex). A-K와 K-B 또한 최단경로

 

👀 특징 

• 순환만 없다면 음수 가중치도 가능하다
• 기본적으로 동적계획법(DP)으로 접근한다.
• ⌛️ 시간복잡도 : θ(V³) (V는 노드의 수) ➡️ 다익스트라 알고리즘보다 느리기 때문에 노드의 수가 적을 때 사용해야 함.

 

🕹️ 플로이드 워셜 과정

다이나믹 프로그래밍(DP) 기법으로 접근하고 인접행렬을 이용하여 각 노드 간 최소 비용을 구한다. 

모든 노드에서 모든 노드로 가는 최소 비용을 단계적으로 갱신하면서 진행되는 알고리즘으로 노드에서 노드로 가는 간선의 개수가 0개부터 시작해서 N개(총 노드의 개수)까지 모두 고려해서 최소 비용을 구한다.

 

1️⃣ 0개의 간선을 거쳐서 모든 노드에서 모든 노드로 가는 경우 

: 자기 자신에서 자기 자신의 노드로 가는 경우뿐이다. 초기 인접 행렬의 값은 자기 자신에서 자기 자신으로 가는 경우(=0)를 제외하고는 다른 노드로 갈 수 있는 방법이 없으므로 모두 매우 큰값으로 초기화(INF)한다.

 

 

2️⃣ 1개의 간선을 거쳐서 모든 노드에서 노드로 가는 경우

: 노드에서 노드로 가는 경우가 여러가지인 경우 간선 중에서 최소비용을 선택한다.

 

3️⃣ 2개의 간선을 거쳐서 모든 노드에서 노드로 가는 경우 ➡️ 특정 노드를 거쳐서 해당 노드에 간다. 

: 2 ➡️ 0 ➡️ 0 일 때 최소 비용 = 7

 2 ➡️ 0 ➡️ 1 일 때 최소 비용 = 3 (12이지만, 3이 최소이므로 갱신 X)

 2 ➡️ 0 ➡️ 2 일 때 최소 비용 = 0 (14이지만, 0이 최소이므로 갱신 X)

 2 ➡️ 0 ➡️ 3 일 때 최소 비용 = 9 (10이었으나, 9가 최소이므로 갱신 !)

 2 ➡️ 0 ➡️ 4 일 때 최소 비용 = 8 (INF이었으나, 8이 최소이므로 갱신 !)

💡 간선 0개 ~ N개를 거쳐서 해당 노드로 가는 비용 중 최솟값 모두 고려 가능

 

---

 

👩‍💻 플로이드 워셜 코드 구현

public class FloydWarshall{

	static int N, M;
    static int[][] dist;
    static int INF = 100000000;
    
    public static void main(String[] args) throws Exception{
    
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        
        dist = new int[N][N];
        
        for(int i=0; i<N; i++){
        	for(int j=0; j<N; j++){
            	if(i==j){
                	dist[i][j] = 0;
                    continue;
                }
                dist[i][j] = 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 cost = Integer.parseInt(st.nextToken());
            
            // 가는 경로가 하나가 아닐 수 있으므로 최소 비용을 저장
			dist[a][b] = Math.min(dist[a][b], cost);
			dist[b][a] = Math.min(dist[b][a], cost);
        }
        
        // 플로이드 워셜 알고리즘
        // 노드를 1개부터 N개까지 거쳐가는 경우 모두 고려 
        for(int k=0; k<N; k++){
        	// 노드 i에서 j로 가는 경우
            for(int i=0; i<N; i++){
            	for(int j=0; j<N; j++){
                	// k번째 노드를 거쳐가는 비용이 기존 비용보다 더 작은 경우 갱신
					// 또는 연결이 안되어있던 경우(INF) 연결 비용 갱신.
					dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}