[알고리즘] Floyd-Warshall(플로이드 워셜)알고리즘이란?

군자·2024년 7월 24일

알고리즘 플로이드 워셜

코딩테스트

목록 보기

7/10

자! 개수치플 벌칙이 있는 코테가 얼마 남지 않은 관계로 알고리즘 머리에 때려넣기 시작하겠습니다~

📌 Floyd-Warshall(플로이드 워셜)알고리즘이란?

🧑🏻‍💻 출발점에서 다른 점들을 향한 최단거리가 아니라 그냥 모든 지점간의 최단거리를 확인하고 싶어!

😈 고럼 그냥 다익스트라를 모든 정점에다 돌리면 안되나?

위와 같은 말도 맞는 말이지만... 실제로 모든 정점에다 돌리게 되면 우선순위를 쓴 최악의 경우, $O(V^3logV)$ 라는 말도안되는 시간복잡도가 나오게 된다. 그렇다면 이제 다른 방법을 고려해야 한다!

// 왜 .. O(V^3logV)이런 시간 복잡도가 나오죠? 에 대한 대답!
원래는 O(ElogV)가 다익스트라+우선순위큐 의 시간 복잡도였던건 기억 할 것이다.
이때 모든 정점에 대해 구해야 하므로 V가 곱해지게 되고, 만약 모든 정점이 연결이 되어있다면,
E = V^2이 될 것이다. 결국 O(V^3logV)이라는 굉장히 답답해지는 알고리즘이 된다.

따라서 모든 쌍에 대해 최단거리를 구하기 위해 ‼️플로이트 워셜‼️ 이 등장하게 된다!

플로이드 워셜 알고리즘은 다익스트라에서 더 나아간 알고리즘이기 때문에 유사한 개념을 공유한다.
다만 좀 다른 점은 A ➡️ B의 경로보다 A ➡️ X ➡️ B 경로가 더 짧다면 해당 경로로 갱신을 해준다는 것이 좀 다르다.

📌 풀이방법

자~ 다시 수도코드를 보며 이해해보자!

🔍 초기 설정

function floyd(graph)
	set dist = V * V array initilaized to INF
    for each edge(u, v)
    	dist[u][v] = length(u, v);

너무 당연한 설정이다!
1. 그래프 배열을 만들고 전부 INF로 초기화해준다.
2. 수도코드에는 없지만, dist[i][i]는 0으로 초기화한다.
3. 거리값이 주어졌다면 다 해당 거리값으로 초기화해준다.

🔍 이동 시작!

for k 1 ... V
	for i 1 ... V
    	for j 1 ... V
        	if dist[i][j] > dist[i][K] + dist[k][j];
            	dist[i][j] = dist[i][K] + dist[k][j];

자. 이부분이 포인트다.
일단 난 처음에 보고 뭔소리지 생각했고, 설명을 들어도 무슨소리지 라고 생각했다.

k는 중간에 경유하는 정점이다. 위에서도 말했지만, 플로이드 워셜은
A ➡️ B의 경로보다 A ➡️ X ➡️ B 경로가 더 짧다면 해당 경로로 갱신해주는 알고리즘이다.
그래서 중간에 k를 둔다.

이거 근데 반복문 순서가 중요하다!!! k가 가장 바깥에 와야한다. 이거 안지키면 제대로 된 최단거리값이 안나올수도..

📌 시간복잡도

아무래도 반복문이 3개이다 보니, $O(V^3)$ 라는 과하게 긴 시간복잡도가 나온다. 따라서 정점 수가 적거나, 모든 쌍에 대해 구해야 할 때 사용하는게 좋다.

그리고 정점이 너무 많다면, 필요한 지점에만 다익스트라를 돌리는 것도 방법이다.

📌 최종코드

class Edge{
	int x, y, weight;
    
    public Edge(int x, int y, int z){
    	this.x = x;
        this.y = y;
        this.weight = weight;
    }
};

public class Main{
	public static int MAX_N = 5;
    public static int[][] graph = new int[MAX_N+1][MAX_N+1];
    
	public static void main(String[] args){
    	int n = 5, int m = 8;
        
        Edge[] edges = new Edge[]{
            new Edge(-1, -1, -1),
            new Edge(2, 1, 3),
            new Edge(1, 4, 3),
            new Edge(4, 2, 1),
            new Edge(5, 2, 4),
            new Edge(5, 4, 2),
            new Edge(4, 3, 2),
            new Edge(3, 4, 1),
            new Edge(1, 3, 6)
        };
        
        // dist 초기값을 전부 아주 큰 값으로 설정
        // INT_MAX 그 자체로 설정하면
        // 후에 덧셈 진행시 overflow가 발생할 수도 있으므로
        // 적당히 큰 숫자로 적어줘야함에 유의!
        for(int i = 1 ; i <= n; i++){
        	for(int j = 1; j <=n; j++){
            	dist[i][j] = (int)1e9;
            }
            dist[i][i] = 0;
        }
        
        for(int i = 1; i <= n; i++){
        	int x = edges[i].x;
            int y = edges[i].y;
            int weight = edges[i].weight;
            dist[x][y] = weight;
        }
        
        for(int k = 1; k <= n; k++){
        	for(int i = 1; i <= n; i++){
            	for(int j = 1; j <= n; j++){
                	dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        
        for(int i = 1; i <= n; i++){
        	for(int j = 1; j<= n; j++){
            	if(dist[i][j] == (int)1e9)
                	System.out.println("-1\n");
                else
                	System.out.println(dist[i][j] + " ");
            }
            System.out.println();
        }
    }
}