[Arogorithm]그래프 - 플로이드워셜

플로이드 워셜은 그래프에서 최단 거리를 구하는 알고리즘이다.
최단 거리 문제는 다익스트라, 벨만포드, 플로이드 워셜이 있다.

기능	특징	시간복잡도
모든 노드 간에 최단 경로 탐색	음수 가중치 에지가 있어도 수행가능 동적 계획법의 원리를 이용해 알고리즘에 접근	O(V^3)

시간복잡도가 매우 높은 편으로 V가 크면 안 쓰는 것이 좋다.  V가 200개 정도면 된다. 

 

📝 핵심 이론

플로이드 워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때 최단경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다. 

즉, 1~5까지의 최단 경로를 구했을 때 인접 노드가 아닌 1~4까지의 최단 경로도 1~5경로와 같다.
대신 출발과 인접하지 않는 조건이다.(전체의 최단 경로는 각 부분의 최단 경로로 이루어져 있다는 것)

 

 

위 이론으로 점화식을 만들 수 있다.

점화식

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

 

📝 수행 과정

1. 리스트를 선언하고 초기화하기

D[S][E]와 같은 리스트를 초기화한다. 초기화 시 자신칸을 제외하고 모두 무한대로 해둔다.

 

2. 최단 거리 리스트에 그래프 데이터 저장하기

들어온 그래프 데이터를 저장해주면 된다.

3. 점화식으로 리스트 업데이트하기

플로이드 워셜의 3중 for문으로 구현하면 된다.

        for (int k = 1; k <= N; k++) {        // 중간 노드
            for (int s = 1; s <= N; s++) {    // 시작 노드
                for (int e = 1; e <= N; e++) { // 종료 노드
                       dist[s][e] = Math.min(dist[s][e],dist[s][k] + dist[k][e]);
                }
            }
        }

 

 

---

완성된 리스트는 모든 노드 간의 최단 거리를 알려준다. 그러나 모든 노드간의 최단 거리를 확인해주기 때문에 시간복잡도가 길어 조심히 사용하는게 좋다.