[알고리즘] Floyd Warshall

그래프에서 정점끼리의 최단 경로를 구하는 방법은 여러가지가 있습니다. 플로이드 와샬 알고리즘에 대해서 알아보기 전에 이에 대해서 간단히 살펴보도록 하겠습니다.

• 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제
• single source and single destination shortest path problem
• 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
• single source shortest path problem
• 하나의 목적지로가는 모든 최단 경로를 구하는 문제
• single destination shortest path problem
• 모든 최단 경로를 구하는 문제
• all pairs shortest path problem

 

알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

📌 플로이드-워셜(Floyd-Warshall) 알고리즘이란?

• 모든 최단 경로를 구하는 알고리즘

---

🔍 플로이드-워셜 알고리즘의 과정

모든 노드 간의 최단거리를 구해야 하므로 2차원 인접 행렬을 구성합니다. 알고리즘은 여러 라운드로 구성됩니다. 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복합니다.

초기 그래프를 인접행렬로 나타내면 다음과 같습니다. INF는 해당 노드에서 특정 노드까지 가는 길이 없다는 뜻입니다.

05INF91

5	0	2	INF	INF
INF	2	0	7	INF
9	INF	7	0	2
1	INF	INF	2	0

---

• ROUND 1 : 1번 노드를 새로운 중간 노드로 설정

이 그래프는 1번부터 5번 노드까지 존재하므로 알고리즘은 총 5라운드의 과정을 거칩니다. 즉, 모든 노드들을 중간 노드로 선정하는 과정을 각 라운드마다 거칩니다. 예를 들어 2라운드는 2번 노드가 중간 노드이며, 3라운드는 3번 노드가 중간 노드가 될 것입니다.

2번에서 4번으로 가는 길은 원래 없었으나, 1번 노드를 중간 노드로 선정할 경우 2-1-4(길이 5+9=14) 로 갈 수 있게 됩니다. (업데이트된 길이는 📍로 표시)

05INF91

5	0	2	14📍	6📍
INF	2	0	7	INF
9	14📍	7	0	2
1	6📍	INF	2	0

---

• ROUND 2 : 2번 노드를 새로운 중간 노드로 설정

1번-3번 노드를 잇는 경로, 3번-5번 노드를 잇는 경로가 새로 생기게 됩니다.

057📍91

5	0	2	14	6
7📍	2	0	7	8📍
9	14	7	0	2
1	6	8📍	2	0

---

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

 

 

기본 코드

package algorithm;

public class FloydWarshall {

	public static void main(String[] args) {
		int[][] a = {{0 ,5 , Integer.MAX_VALUE, 8}, 
					 {7, 0, 9, Integer.MAX_VALUE},
					 {2, Integer.MAX_VALUE, 0, 4},
					 {Integer.MAX_VALUE, Integer.MAX_VALUE, 3, 0}};
		
		floydWarshall(a);
	}
	
	public static void floydWarshall(int[][] a) {
		int[][] d = a;
		
		//k는 방문 노드
		for(int k = 0; k < a.length; k++) {
			//i는 출발 노드
			for(int i = 0; i < a.length; i++) {
				//j는 도착 노드
				for(int j = 0; j < a.length; j++) {
					if(d[i][k] + d[k][j] > 0 && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
				}
			}
		}
		
		for(int i = 0; i < d.length; i++) {
			for(int j = 0; j < d.length; j++) {
				System.out.print(d[i][j] + " ");
			}
			System.out.println();
		}
	}

}