[알고리즘] 플로이드 와샬 (Floyd-Warshall) 알고리즘

플로이드 와샬 (Floyd-Warshall)

• 유향 그래프에서 '모든 정점' → '모든 정점' 까지의 최단 경로를 구하는 알고리즘이다.
• 시간복잡도 : O(N ^ 3) , (N은 노드의 수)
• 삼중 반복문을 사용하기에 N의 크기가 상대적으로 적을 때 사용해야한다.

 

알고리즘

1. 정점 i → 정점 j 까지의 최단 거리를 저장하는 dist[][] 배열을 둔다.
2. dist 초기화
   1. i == j : 0
   2. i → j 까지의 간선이 존재한다면 dist[i][j] = w[i][j]
   3. i → j 까지의 간선이 존재한다면 dist[i][j] = INF (무한대)
3. 삼중 반복문 실행
   1. 첫번째 반복문 k = 1 ~ N : 거쳐가는 정점
   2. 두번째 반복문 i = 1 ~ N : 시작점
   3. 세번째 반복문 j = 1 ~ N : 도착점
   4. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
      1. 즉, i에서 j로 갈 때, k를 거쳐가는 것이 더 가깝다면 대입

 

예시 (백준 11404번)

11404번: 플로이드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static int V, E;
	static int dist[][];
	static final int INF = 100000 * 100 + 1;

	public static void solution() throws Exception
	{
		V = Integer.parseInt(br.readLine());
		E = Integer.parseInt(br.readLine());

		dist = new int[V+1][V+1];

		for(int i = 0;i <= V;i++)
		{
			for(int j = 0;j <= V;j++)
			{
				if(i != j)
					dist[i][j] = INF;
			}
		}

		for(int i = 0;i < E;i++)
		{
			StringTokenizer strtok = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(strtok.nextToken());
			int to = Integer.parseInt(strtok.nextToken());
			int weight = Integer.parseInt(strtok.nextToken());

			dist[from][to] = Math.min(dist[from][to], weight);
		}

		floydWashall();

		for(int i = 1;i <= V;i++)
		{
			for(int j = 1;j <= V;j++)
			{
				if(dist[i][j] == INF)
					bw.write("0 ");
				else
					bw.write(dist[i][j] + " ");
			}
			bw.write("\n");
		}
	}

	static void floydWashall()
	{
		for(int k = 1;k <= V;k++)
		{
			for(int i = 1;i <= V;i++)
			{
				for(int j = 1;j <= V;j++)
				{
					dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
	}
	

	public static void main(String[] args) {
		try
		{
			solution();
			bw.close();
			br.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}