플로이드-워셜(floyd-warshall)

---

정의

플로이드-워셜 알고리즘은 그래프에서 모든 쌍의 최단거리를 구하는 알고리즘입니다.
이 알고리즘은 동적 계획법을 사용하여 모든 노드 쌍 사이의 최단 경로를 효율적으로 찾을 수 있습니다.

특징

모든 노드 쌍 간의 최단거리를 탐색합니다:
플로이드-워셜 알고리즘은 그래프의 모든 노드 쌍에 대해 최단거리를 계산합니다. 이는 네트워크 분석, 최단경로 문제 등 다양한 분야에서 유용합니다.

 

엣지는 양수와 음수 모두 가능합니다:
플로이드-워셜 알고리즘은 음수 가중치를 가진 엣지도 처리할 수 있지만, 음수 사이클이 존재해서는 안 됩니다. 음수 사이클이 있는 경우 최단거리를 계산할 수 없습니다.

알고리즘 동작 과정

플로이드-워셜 알고리즘의 기본적인 동작 과정은 다음과 같습니다:

1. 초기화: 각 노드 쌍 간의 거리를 저장하는 2차원 배열을 초기화합니다. 동일한 노드 간의 거리는 0, 직접 연결된 노드 간의 거리는 엣지의 가중치로 설정하고, 연결되지 않은 노드 간의 거리는 무한대로 설정합니다.
2. 동적 계획법 사용: 중간 노드를 거쳐 가는 경로가 직접 가는 경로보다 짧은지 확인하고, 더 짧은 경로를 찾으면 거리를 갱신합니다.
   핵심적인 부분인데, A→B노드 까지 최단 경로를 구했다고 가정했을 때, 최단경로(A→B) 사이에 K노드가 존재한다면?
   → 그것을 이루는 부분 경로도 최단 경로라는 것 (A→L, K→B)
   점화식:
   
   F[S][E] = Math.min(F[S][K]+F[K]E], F[S][E])
3. 반복: 모든 노드에 대해 위 과정을 반복하여 최단거리를 계산합니다.
   
   

시간 복잡도

플로이드-워셜 알고리즘의 시간 복잡도는 다음과 같습니다:

• O(V^3) (V: 노드의 수)

이는 세 개의 중첩된 반복문을 통해 모든 노드 쌍에 대해 경로를 확인하기 때문입니다.

 

 

예제

간단한 예제를 통해 플로이드-워셜 알고리즘의 동작을 살펴보겠습니다.

그래프가 다음과 같다고 가정해보겠습니다.

S==E는 0, 다른칸은 MAX로 초기화 후, 인접행렬을 만들어 줍니다.

   A   B   C   D
A  0   3  INF  7
B  8   0   2  INF
C  5  INF  0   1
D  2  INF INF  0

 

1. 초기화: 위와 같이 각 노드 쌍 간의 거리를 설정합니다.
2. 동적 계획법 사용: 모든 노드를 중간 노드로 사용하여 경로를 갱신합니다.
3. 반복: 모든 노드에 대해 경로를 확인하고 갱신합니다.

최종 결과:

   A   B   C   D
A  0   3   5   6
B  8   0   2   3
C  5   8   0   1
D  2   5   7   0

 

예제 코드

import java.util.Arrays;

public class FloydWarshallAlgorithm {
    final static int INF = 99999;

    public static void floydWarshall(int[][] graph) {
        int V = graph.length;
        int[][] dist = new int[V][V];

        // 초기화
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // 플로이드-워셜 알고리즘
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        printSolution(dist);
    }

    public static void printSolution(int[][] dist) {
        int V = dist.length;
        System.out.println("Shortest distances between every pair of vertices:");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 3, INF, 7},
            {8, 0, 2, INF},
            {5, INF, 0, 1},
            {2, INF, INF, 0}
        };

        floydWarshall(graph);
    }
}