[java] 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

1. 플로이드 워셜 알고리즘이란,

그래프에서 가능한 모든 노드 쌍에 대한 최단 거리를 구하는 알고리즘입니다.

​

* 다익스트라 알고리즘은, 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이고,

* 플로이드-워셜 알고리즘은, 한 번 실행하여 모든 노드​ 간의 최단 거리를 구하는 알고리즘입니다.

​

* 플로이드 워셜 알고리즘은, 다익스트라 알고리즘과 다르게 음의 간선도 사용할 수 있다.

 

---

2. 과정

​

* 플로이드 워셜 알고리즘은 모든 노드간의 경로를 구하기때문에 2차원 배열이 필요합니다.

​

초기 행렬

​

* 노드의 개수만큼 라운드를 반복하여 각각의 해당 하는 노드를 중간 노드로 설정합니다.

​

예를 들어,

1) 1번 라운드에는, 1번 노드가 중간노드가 되어 가능한 모든 경로를 갱신합니다.

ex) 2-1-4 = 14

---

Round 1

1번노드가 중간 노드

---

Round 2

2번노드가 중간 노드

이런 과정으로 5번 노드를 중간 노드로 선정하는 라운드까지 모두 거치면 행렬에는 모든 노드 간 최단 거리가 들어가게 됩니다.

​

 

---

3. 소스코드

플로이드-워셜 알고리즘은 3중 반복문을 이용하고,

시간복잡도가 O(n^3)으로 그래프의 크기가 작을때 용이 합니다.

 

Arrays.fill(list[][], Null)   //배열 초기화

for(int k = 1; k<= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j<=n; j++){
            list[i][j] = min(list[i][j], list[i][k]+list[k][j]);
        }
    }
}

​- k를 가운데 노드로 두어 k를 중간노드로 삼을 때와, 아닐 때를 비교하면서 최소값으로 업데이트 합니다.