Algorithm - 플로이드 워셜 알고리즘

플로이드 워셜 알고리즘

 

그래프가 주어졌을 때 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘입니다. 한 점에서 다른 정점으로의 모든 최단 경로를 구하는 다익스트라 알고리즘은 음의 가중치를 사용하지 못하지만 플로이드 워셜 알고리즘은 음의 가중치를 가진 그래프도 계산 가능합니다.

 

플로이드 워셜 알고리즘 과정

 

1. 그래프를 2차원 배열로 나타내고 i행 j열에 i번 정점에서 j번 정점으로 가는 가중치를 저장합니다. 

 

2. i 행 i 열 값은 0으로 저장하고, i번 정점에서 j번 정점으로 갈 수 없는 경우 INF (매우 큰 수)를 저장합니다.

 

3. k를 중간점으로 삼고, i번 정점에서 j번 정점으로 가는 가중치보다 정점 i -> 정점 k , 정점 k -> 정점 j로 가는 정점의 가중치가 작다면 i행 j열 값을 업데이트한다.

 

4. 모든 정점에 대하여 3의 과정을 반복한다.

 

코드

for (int i = 1 ; i <= N ; i++) {
    for (int j = 1 ; j <= N ; j++) {
        if (i == j) dist[i][j] = 0;
        else if (adj[i][j] != 0) dist[i][j] = adj[i][j];
        else dist[i][j] = INF;
    }
}

// 정점의 개수 N
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문이 3개 중첩되어 있어 O(N^3) 시간복잡도를 보인다. N의 크기가 1000을 넘어가면 다른 알고리즘을 고려해 보아야 한다.