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

플로이드-와샬 알고리즘이란?

플로이드-와샬(Folyd-Warshall) 알고리즘

• 그래프의 최단 경로를 구하는 알고리즘 중 하나
• 모든 정점들 간의 최단 거리를 구함(테이블을 채운다고 볼 수 있음)
• 음수 사이클이 없어야 함 (음수 가중치는 허용)
• 그래프 비용 인접 행렬로 표현되어 있다고 가정
• 시간 복잡도 O(n^3)
• 동적 계획법(dp) 이용

---

원리

경유지 k, 출발 정점 i, 도착 정점을 j라고 하자. 그래프의 연결 경로 graph라는 이차원 배열에 저장되어 있다.

graph[i][j]는 i에서 j까지 가는 최단 거리를 나타낸다.

graph[i][k] + graph[k][j]는 i에서 j까지 가는데 k를 경유하여 가는 거리이다.

만약, graph[i][j] > graph[i][k] + graph[k][j]면 i부터 j까지 가는데 k를 거쳐서 가는 것이 더 최단 거리임을 의미한다.

따라서 graph[i][j]는 graph[i][k] + graph[k][j]로 갱신해 준다.

graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

위와 같이 계산값을 저장하고, 갱신해 나가는 것에서 동적 계획법이 사용된다.

위와 같은 그림을 기준으로 생각해 보자.

초기 그래프

시작/끝	1	2	3	4
1	0	4		6
2	3	0		9
3	5	9	0	4
4			2	0

---

모두 1번을 거쳐가게 만든 그래프

시작/끝	1	2	3	4
1	0	4		6
2	3	0		9
3	5	9	0	4
4			2	0

---

모두 2번을 거쳐가게 만든 그래프

시작/끝	1	2	3	4
1	0	4		6
2	3	0		9
3	5	9	0	4
4			2	0

---

모두 3번을 거쳐가게 만든 그래프

시작/끝	1	2	3	4
1	0	4		6
2	3	0		9
3	5	9	0	4
4	7	11	2	0

---

모두 4번을 거쳐가게 만든 그래프

시작/끝	1	2	3	4
1	0	4	8	6
2	3	0	11	9
3	5	9	0	4
4	7	11	2	0

 

최종적으로 모든 점과 점 사이의 최단거리가 저장되는 것이다.

---

구현

//이중 배열에 저장된 그래프, 정점의 개수 넘겨줌
public static void floyd(int[][] graph, int n) {
    // 경유지
    for (int k = 1; k <= n; k++) {
        // 출발지
        for (int i = 1; i <= n; i++) {
            //도착지
            for (int j = 1; j <= n; j++) {
                graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
            }
        }
    }
}

삼중 반복문을 통해 기록된다.

예시를 보자면

k = 1, i = 1일 때 -> 1번 에서 시작하여 j번으로 갈 때 Math.min(원래 1->j , k(1)을 경유해서 갈 때)를 모두 방문하는 것이다.

따라서, O(N^3)의 시간 복잡도를 갖게 되는 것이다.

---

vs 다른 최단 거리 알고리즘

벨만 포드 알고리즘

[알고리즘/Java] 벨만-포드(Bellman-Ford) 알고리즘

2025.02.04 - [문제 풀이/도구정리] - [도구정리] 다익스트라 알고리즘

[도구정리] 다익스트라 알고리즘