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를 중간노드로 삼을 때와, 아닐 때를 비교하면서 최소값으로 업데이트 합니다.
'Java > Java 문법' 카테고리의 다른 글
[Java] Map 모든 인덱스 조회하기 (0) | 2021.07.22 |
---|---|
[JAVA] 우선순위 큐(priorityQueue) (0) | 2021.04.28 |
[java] 선택정렬 (Select Sort) (0) | 2021.04.28 |
[java] 객체 정렬 Comparable과 Comparator (0) | 2021.04.28 |
[JAVA] 배열 초기화(Arrays.fill() 메소드 / 배열 값 채우기) (1) | 2021.04.28 |