플로이드 와샬 알고리즘 (JAVA)

 

 

언제 사용하는가?

 

이전 포스팅에서 다루었듯 최단거리 혹은 최소비용을 구하는것에 적합한 알고리즘은

BFS, 데이크스트라 알고리즘 등이 있다.

 

먼저 둘의 차이는 데이크스트라 알고리즘 포스팅에서 다루었으니 넘어가도록 하고

이번에 다뤄볼 플로이드 와샬 알고리즘과 데이크스트라 알고리즘의 차이부터 짚고 넘어가고자 한다.

 

간단히 말해서 모든 정점에서 하나의 정점으로 가는 최단거리를 구하고 싶을땐, 데이크 스트라

모든 정점에서 모든 정점으로 가는 최단거리를 구하고 싶을 땐 플로이드 와샬 알고리즘을 사용한다.

 

자세히 들어가자면, 데이크스트라 알고리즘은 그때 그때 마다 힙에서 최소비용에 해당하는 정점 하나씩

꺼내 비교후 갱신하는 방식이지만 플로이드 와샬은 거쳐하는 모든 정점을 확인해 갱신하는 방식으로

동작한다.

 

 

 

어떻게 사용하는가?

 

한가지 예시를 들어 동작원리를 설명하도록 하겠다.

 

먼저 다음과 같은 그래프가 있다고 가정하겠다.

 

 

 

 

이제 각 노드의 간선 관계를 표로 표현 한다면 다음과 같이 표현이 가능할것이다.

 

0	2	3	1	10
♾️	0	♾️	2	♾️
8	♾️	0	1	1
♾️	♾️	♾️	0	3
7	4	♾️	♾️	0

 

 

즉 1행 1열은 1번 정점에서 1번 정점으로 가는 간선의 가중치를 의미하고

1행 2열은 1번 정점에서 2번 정점으로 가는 간선의 가중치를 의미한다.

이때 가중치가 없는 다시 말해 바로 갈수 있는 간선이 없는 경우 우선 무한으로 표시를 해주도록 한다.

 

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점을 거쳐가는 과정을 통해 모든 정점으로의 최단거리를 

구한다.

 

즉 현재 1번 정점에서 5번 정점으로 가는 가중치는 표에 나와있듯 10이지만

1번 정점에서 4번 정점을 거쳐 4번 정점에서 5번 정점으로 진행한다면

1 (1번정점에서 4번 정점) + 3 (4번 정점에서 5번 정점) < 10 (1번 정점에서 5번 정점)

이므로 4로 갱신 될것이다. 이런 과정을 모든 정점을 거쳐가며 확인하면 된다.

 

그럼 거쳐가는 정점이 1번 정점인 경우를 살펴보도록 하겠다.

 

0	2	3	1	10
♾️	0	♾️ ✔️	2	♾️
8	♾️	0	1	1
♾️	♾️	♾️	0	3
7	4	♾️	♾️	0

 

 

2행 3열 부터 살펴보면 2번정점 ➡️ 3번 정점의 간선은 없으므로 무한이다.

이때 1번 정점을 거쳐간다고 했을 경우 2번 정점 ➡️ 1번 정점 ➡️ 3번 정점 인데

2번 정점 ➡️ 1번 정점이 무한이므로 이 경우 최소비용은 갱신 되지 않는다.

 

즉 2번 정점에서 1번 정점을 거쳐가는 모든 경우의 수는 무한이라 갱신되지 않으므로 생략하도록 하겠다.

 

 

0	2	3	1	10
♾️	0	♾️	2	♾️
8	♾️✔️	0	1	1
♾️	♾️	♾️	0	3
7	4	♾️	♾️	0

 

 

3행 2열의 경우 현재 3번정점 ➡️ 2번 정점의 간선의 가중치인 무한과

3번 정점 ➡️ 1번 정점 ➡️ 2번 정점을 비교해주면 되는데

3번 정점 ➡️ 1번 정점의 가중치는 8, 1번 정점 ➡️ 2번 정점의 가중치는 2

8 + 2 < ♾️ 이므로 최소비용은 갱신된다.

 

그리고 이어서 3행 모두를 같은 방법으로 살펴보면 갱신되지 않음을 확인 할 수있다.

 

0	2	3	1	10
♾️	0	♾️	2	♾️
8	10	0	1	1
♾️✔️	♾️	♾️	0	3
7	4	♾️	♾️	0

 

 

4행은 4번정점 ➡️ 1번 정점이 무한이므로 모두 갱신될수 없다.

 

 

0	2	3	1	10
♾️	0	♾️	2	♾️
8	10	0	1	1
♾️	♾️	♾️	0	3
7 ✔️	4	♾️	♾️	0

 

 

이어서 5행은 5번정점 ➡️ 1번 정점이 7이고,

1번 정점 ➡️ 2번 정점 : 2

1번 정점 ➡️ 2번 정점 : 3

1번 정점 ➡️ 2번 정점 : 1

1번 정점 ➡️ 2번 정점 : 10

 

이므로 각각 비교해 갱신해준다면

 

0	2	3	1	10
♾️	0	♾️	2	♾️
8	10	0	1	1
♾️	♾️	♾️	0	3
7	4	10	8	0

 

다음과 같이 갱신된 결과를 볼 수 있겠다.

 

 

위의 과정을 반복해 모든 최소비용이 갱신된 결과를 표로 나타낸다면 다음과 같은 결과를 얻을수 있다.

 

 

0	2	3	1	4
12	0	15	2	5
8	5	0	1	1
10	7	13	0	3
7	4	10	6	0

 

 

그럼 이제 이를 소스로 구현해 보도록 하겠다.

 

먼저 예시로 들은 그래프와 동일하게 초기값을 넣어주고 시작하겠다.

public class FloydWarshall {

	private static final int INF = Integer.MAX_VALUE;

	private final int[][] edges = {
			{ 0, 2, 3, 1, 10 },
			{ INF, 0, INF, 2, INF },
			{ 8, INF, 0, 1, 1 },
			{ INF, INF, INF, 0, 3 },
			{ 7, 4, INF, INF, 0 }
	};
}

 

 

그리고 거쳐갈 정점 > 시작할 정점 > 도착할 정점으로 3중 반복문을 통해 구현하도록 하겠다.

 

이때 오버플로우를 막아주기 위해 무한대를 처리할 별도의 메소드도 생성해주도록 하겠다.

 

	void floydWarshall() {
		for(int k = 0; k < edges.length; k++) { // 거쳐갈 정점
			for(int i = 0; i < edges.length; i++) { // 시작할 정점
				for(int j = 0; j < edges.length; j++) { // 도착할 정점
					edges[i][j] = min(edges[i][j], edges[i][k], edges[k][j]);
// 현재 정점 = 현재 정점 (비교) 시작정점 ➡️ 거쳐갈 정점 + 거쳐갈 정점 ➡️ 도착 정점
				}
			}
		}
	}
	
	private int min(int current, int start, int end) {
		if(start == Integer.MAX_VALUE || end == Integer.MAX_VALUE) {
			return current;
		}
		return Math.min(current, start + end);
	}

 

 

이제 이를 실행시켜 모든 최단비용을 출력한다면 다음과 같은 결과를 얻을 수 있다.

 

 

 

이는 위에서 마지막으로 정리한 표와 동일한 결과를 갖는것을 확인 할 수 있다.

 

아래는 코드의 전문이다.

 

package floydWarshall;

public class FloydWarshall {

	private static final int INF = Integer.MAX_VALUE;

	private final int[][] edges = {
			{ 0, 2, 3, 1, 10 },
			{ INF, 0, INF, 2, INF },
			{ 8, INF, 0, 1, 1 },
			{ INF, INF, INF, 0, 3 },
			{ 7, 4, INF, INF, 0 }
	};
	
	void floydWarshall() {
		for(int k = 0; k < edges.length; k++) {
			for(int i = 0; i < edges.length; i++) {
				for(int j = 0; j < edges.length; j++) {
					edges[i][j] = min(edges[i][j], edges[i][k], edges[k][j]);
				}
			}
		}
	}
	
	private int min(int current, int start, int end) {
		if(start == Integer.MAX_VALUE || end == Integer.MAX_VALUE) {
			return current;
		}
		return Math.min(current, start + end);
	}
	
	void printedges() {
		for(int i = 0; i < edges.length; i++) {
			for(int j = 0; j < edges.length; j++) {
				System.out.print(edges[i][j] + "\t");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		FloydWarshall floyd = new FloydWarshall();
		floyd.floydWarshall();
		floyd.printedges();
	}

}