플로이드-워셜 알고리즘

플로이드-워셜 알고리즘이란?

플로이드-워셜 알고리즘은 음수 사이클이 없는 그래프내의 각 모든 정점에서 각 모든 정점에 까지의 최단 거리를 모두 구할 수 있는 알고리즘입니다. 이 알고리즘은 다익스트라 알고리즘과는 달리 음의 가중치를 가진 간선을 포함한 그래프에서도 사용할 수 있습니다. 하지만 다익스트라 알고리즘보다 시간 복잡도가 더 높기 때문에, 그래프가 아주 크거나 음의 가중치를 포함하지 않는 경우에는 다익스트라 알고리즘이 더 효율적일 수 있습니다.

플로이드-워셜 알고리즘의 경우에도 다이나믹 프로그래밍 기법을 사용하고, 인접 행렬을 이용하여 각 노드간 최소 비용을 계산합니다.

구현 방식

한 노드에서 다른 노드까지의 최단거리는 한 노드에서 중간노드 까지의 최단거리와 중간 노드에서 다른 노드까지의 최단거리로 봐도 무방하다고 앞서 살펴보았습니다. 플로이드-워셜 알고리즘은 세가지의 노드를 선택해서 한 노드에서 중간 노드 까지의 거리 + 중간 노드에서 목적지 노드까지의 거리를 반복해서 초기화 해줍니다.

동작 과정

1. 값을 입력 받아서 각 edge별 가중치 값을 dist[][] 배열에 넣어주고, 나머지 값은 INF로 초기화 해준다. (i == j Index의 경우 0으로 초기화)
2. 그 후 삼중 for 반복문을 사용
   1. 각 for문은 0 ~ V - 1까지 총 V번씩 수행 된다.
   2. 각 for문에서 사용되는 초기 값들은 순서대로 중간 노드 → 출발 노드 → 종착 노드의 Index로써 활용된다.

// 플로이드 워셜 알고리즘
	// 노드를 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]);
			}
		}
	}

특징

1. 음의 간선도 사용 가능

2. 다이나믹 프로그래밍 기법 사용 + 인접 행렬 이용

코드

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

/*
Sample Input
5 8
1 2 5
1 5 1
1 3 7
1 4 2
2 3 3
2 4 6
3 4 10
4 5 4
*/

// 플로이드 와샬의 경우 Graph List가 필요하지 않다.
// 또한, 모든 Node에서의 최단 거리를 구하는 것이기 때문에 start 변수도 필요하지 않다.
public class Main {
  static int N, M;
  static int[][] dist;
  public static void main(String[] args) throws IOException {

    // 초기화
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());

    // 플로이드 초기 거리 테이블 초기화
    dist = 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) {
          // 자기 자신으로 가는 길은 최소 비용이 0이다.
          dist[i][j] = 0;
          continue;
        }
        // 자기 자신으로 가는 경우르 ㄹ제외하고는 매우 큰 값(Int값 중에 가장 큰 값으로 설정)
        dist[i][j] = Integer.MAX_VALUE;
      }
    }

    for(int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int n1 = Integer.parseInt(st.nextToken());
      int n2 = Integer.parseInt(st.nextToken());
      int cost = Integer.parseInt(st.nextToken());

      // 가는 경로가 하나가 아닐 수 있다. 따라서 그 중 최소 비용을 저장해두면 된다.
      dist[n1][n2] = Math.min(dist[n1][n2], cost);
      dist[n2][n1] = Math.min(dist[n2][n1], cost);
    }

    // Floyd Warshall Algorithm
    // 노드를 1개부터 N개까지 거쳐가는 경우를 모두 고려한다.
    for(int k = 1; k < N + 1; k++) {
      // 노드 i에서 j로 가는 경우.
      for(int i = 1; i < N + 1; i++) {
        for (int j = 1; j < N + 1; j++) {
          // k번쨰 노드를 거쳐가는 비용이 기존 비용보다 더 작은 경우 갱신
          // 또는 연결이 안되어 있던 경우 (INF) 연결 비용 갱신.
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }

    // 출력
    for(int i = 1; i < N + 1; i++) {
      for(int j = 1; j < N + 1; j++) {
        if(dist[i][j] == Integer.MAX_VALUE) {
          System.out.print("INF ");
        } else {
          System.out.print(dist[i][j] + " ");
        }
      }
      System.out.println();
    }

  }
}

시간 복잡도

모든 노드(V)에 대해서, 3중 for문이 수행되어 지므로 $O(V^3)$의 시간 복잡도를 갖습니다.

굉장히 높은 시간 복잡도를 가지고 있기 때문에 해당 알고리즘을 사용할 때는 입력값의 크기가 어느 정도인지 가늠을 하고 사용해야 합니다.

장단점

장점

1. 모든 노드에 관해서 최단 거리를 구할 수 있다.

단점

1. 너무 오랜 시간이 소모된다.

---

Reference

• [Java]플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) :: TH
• 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘 | ChanBLOG