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

플로이드-워셜 알고리즘

변의 가중치가 음이거나 양인(음수 사이클은 없는) 가중 그래프에서 최단 경로를 찾는 알고리즘.
모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다.

---

점화식

각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.

• i에서 j로 가는 최단거리와 i에서 k를 거쳐 j로 가는 거리를 비교한다.

$$ DP(i, j) = min(DP(i, j), DP(i, k) + DP(k, j)) $$

---

동작 과정

예시 그래프:

 

1) k = 0 (초기 가중치)

i/j	1	2	3	4
1	0	♾️	-2	♾️
2	4	0	3	♾️
3	♾️	♾️	0	2
4	♾️	-1	♾️	0

 

2) k = 1 (1번 노드를 거쳐가는 경우)

i/j	1	2	3	4
1	0	♾️	-2	♾️
2	4	0	2	♾️
3	♾️	♾️	0	2
4	♾️	-1	♾️	0

dp23 = min(dp23, dp21 + dp13) = 2

 

 

3) k = 2 (2번 노드를 거쳐가는 경우)

i/j	1	2	3	4
1	0	♾️	-2	♾️
2	4	0	2	♾️
3	♾️	♾️	0	2
4	3	-1	1	0

dp41 = min(dp41, dp42+dp21) = 3
dp43 = min(dp43, dp42+dp23) = 1

 

 

4) k = 3 (3번 노드를 거쳐가는 경우)

i/j	1	2	3	4
1	0	♾️	-2	0
2	4	0	2	4
3	♾️	♾️	0	2
4	3	-1	1	0

dp14 = min(dp14, dp13 + dp34) = 0
dp24 = min(dp24, dp23 + dp34) = 4

 

 

5) k = 4 (4번 노드를 거쳐가는 경우)

i/j	1	2	3	4
1	0	-1	-2	0
2	4	0	2	4
3	5	1	0	2
4	3	-1	1	0

dp12 = min(dp12, dp14 + dp42) = -1
dp31 = min(dp31, dp34 + dp41) = 5
dp32 = min(dp32, dp34 + dp42) = 1

---

기본 알고리즘

public class Floyd_Warshall {  
    static int INF = 9999999;  
    public static void main(String[] args) throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");  
        int V = Integer.parseInt(st.nextToken());  
        int E = Integer.parseInt(st.nextToken());  
        int[][] adjMatrix = new int[V+1][V+1];  

        for (int i = 1; i <= V; i++) {  
            Arrays.fill(adjMatrix[i], INF);  // 모든 경우를 INF로 초기화
        }  
        for (int i = 1; i <= V; i++) {  
            adjMatrix[i][i] = 0;  // 자신의 노드로 가는 경우는 0으로 설정
        }  

        for (int i = 0; i < E; i++) {  
            st = new StringTokenizer(br.readLine(), " ");  
            int a = Integer.parseInt(st.nextToken());  
            int b = Integer.parseInt(st.nextToken());  
            int c = Integer.parseInt(st.nextToken());  
            adjMatrix[a][b] = c;  // 가중치 저장
        }  

        for (int k = 1; k <= V; k++) {  
            for (int i = 1; i <= V; i++) {  
                if (i == k) continue;  // k번 행의 정보는 갱신되지 않음
                for (int j = 1; j <= V; j++) {  
                    if (i == j || j == k) continue;  // 자신의 노드, k번 열의 정보는 갱신되지 않음
                    adjMatrix[i][j] = Math.min(adjMatrix[i][j], adjMatrix[i][k] + adjMatrix[k][j]);  
                }  
            }  
        }  

        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                if (adjMatrix[i][j] == INF) System.out.print("INF");
                else System.out.print(adjMatrix[i][j]);
            }
            System.out.println();
        }
    }  
}

---

성능

• 노드의 개수가 V개일 때, V번의 단계를 수행한다.
  • 각 단계마다 O(V^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다.
• 총 시간 복잡도는 O(V^3)이다.