플로이드 워셜 알고리즘

플로이드 워셜 알고리즘

특정 노드에서 다른 모든 노드까지의 촤단 경로를 계산하는 다익스트라 알고리즘과 달리, 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 구하는 알고리즘입니다.

다이나믹 프로그래밍 알고리즘의 유형으로, "특정 정점을 거쳐가는 경로" 를 점진적으로 계산하면서 최단 경로를 탐색합니다.

그래프 선언 및 초기화

1. 그래프를 인접행렬로 생성합니다.
2. 직접 연결된 간선이 있으면 가중치를 넣고, 연결이 없으면 무한대 혹은 아주 큰 수를 넣고 초기화합니다.

  int[][] graph = {
            {0, 5, INF, 10},
            {INF, 0, 3, INF},
            {INF, INF, 0, 1},
            {INF, INF, INF, 0}
        };

• graph[i][j] : i번 노드에서 j번 노드로 가는 최단 거리를 의미합니다.

구현

public static void floydWarshall(int[][] graph) {
        int n = graph.length;
        for (int i = 0; i < n; i++) {//중간 정점
            for (int j = 0; j < n; j++) {//시간 정점
                for (int k = 0; k < n; k++) {//도착 정점
                    //j => k로 가는 최단 경로를, j => i => k를 거쳐 가는 최단 경로와 비교하여 갱신.
                    graph[j][k] = Math.min(graph[j][k], graph[j][i] + graph[i][k]);
                    
                }
            }
        }
    }

특징

• 시간 복잡도는 $O(n^3)$ 입니다.
• 음의 가중치가 있어도 동작합니다.