플로이드-와샬 알고리즘

플로이드-와샬 알고리즘은 모든 정점 간의 최단 경로를 찾는 알고리즘으로, 음의 가중치를 가진 그래프에서도 사용할 수 있습니다.

전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루지는 것이 이 알고리즘의 핵심 아이디어이다. (S -> E까지의 최단 거리는 S -> K -> E의 최단 거리와 같다.)  이 원리로 다음과 같은 점화식을 도출할 수 있다.

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

해당 알고리즘은 3중 for 문으로 이루어져 있어 O(V^3)에 시간복잡도를 가지고 있다.

알고리즘 동작 순서

---

1. 초기화: 최단 거리를 저장하는 2차원 배열을 초기화한다. 초기에는 직접적인 간선이 존재하면 해당 가중치를, 그렇지 않으면 무한대(INF)로 설정한다.
2. 동적 프로그래밍을 활용한 갱신: 3중 반복문을 사용하여 각 정점을 거치는 경우를 고려하여 최단 거리를 갱신한다.

class FloydWarshallAlgorithm {
    // INF로  Integer를 사용하려면 graph는 long 배열이어야한다.
    static final int INF = Integer.MAX_VALUE;

    void floydWarshall(long graph[][], int V) {
        // k: 경유지, s: 출발지 , e: 도착지
        for (int k = 0; k < V; k++) {
            for (int s = 0; s < V; s++) {
                for (int e = 0; e < V; e++) {                  
                    // graph[s][e] = Math.min(graph[s][e], graph[s][k] + graph[k][e]);
                    if(graph[s][e] > graph[s][k] + graph[k][e]){
                       graph[s][e] = graph[s][k] + graph[k][e]
                    }
                }
            }
        }
    }
}