[자료구조] 플로이드 워셜 알고리즘 (Java)

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

 

플로이드 워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대한 최단거리를 구하는 알고리즘이다.

이게 무슨소리냐면 아래와 같은 그래프에서 

1 -> 4 로 가는 비용은 8 이지만 

3번 노드를 거쳐서 가면

1 -> 3 : 2

3 -> 4 : 4

이렇게 가는 비용이 6이라 더 짧기때문에

1 -> 4  가는 비용을 6으로 바꿔준다는 얘기이다.

 

이렇게 해서 모든 노드로 가는 최소비용을 구하는것이다.

 

 

이걸 구현하는 방법은 위에서 보여줬듯이

모든 노드를 거쳤을때 가는 비용이 일반적으로 가는 비용보다 큰지를 확인하고 거쳤을때의 비용이 작다면

값을 바꿔주고 아니라면 값을 그대로 냅두는것이다.

 

이걸 위그림을 표로 만든것을 토대로 한번 해보자.

	1	2	3	4
1	0	5	무한	8
2	7	0	9	무한
3	2	무한	0	4
4	무한	무한	3	0

 

1번 노드를 거쳤을때

 

1번 노드를 거치는것이니 [1][]과 [][1]부분은 볼 필요가 없고

자기 자신은 가르키는 부분도 볼필요가없다.

왜냐하면 1번노드는 이미 거쳐서 가고 있기때문에 볼 필요가 없고 자기자신을 가르키는것은 볼필요가 없고 그래프상에도 없기 때문이다.

	1	2	3	4
1	0	5	무한	8
2	7	0	9	무한
3	2	무한	0	4
4	무한	무한	3	0

따라서 우리는 빨간색으로 표시된 부분만 1번 노드를 거치는게 더 빠른지 아닌지를 확인해보면 된다.

 

2->3 을 확인해보자

2->3 : 9

2->1 + 1->3 : 7+무한

 

9가 더 빠르니 그대로 냅둔다.

 

2->4 을 보자

2->4 : 무한

2->1 + 1->4 : 7+8

1을 거쳐서 가는 15가 너 빠르니 15로 바꿔주자.

	1	2	3	4
1	0	5	무한	8
2	7	0	9	15
3	2	무한	0	4
4	무한	무한	3	0

 

3->2를 보자.

3->2 : 무한

3->1 + 1->2 : 2+5

7이 더 빠르니 바꿔준다.

	1	2	3	4
1	0	5	무한	8
2	7	0	9	15
3	2	7	0	4
4	무한	무한	3	0

3->4를 보자.

3->4 : 4

3->1 + 1-> 4 : 2+8

4가 더 빠르니 냅둔다.

 

4->2를 보자.

4->2 : 무한

4->1 + 1->2 : 무한 + 5

무한 그대로 둔다.

 

4->3을 보자.

4->3 : 3

4->1 + 1->3 : 무한 + 무한

3그대로 둔다.

 

그럼 1번 노드를 거쳤을때의 최소비용은 아래와 같다.

	1	2	3	4
1	0	5	무한	8
2	7	0	9	15
3	2	7	0	4
4	무한	무한	3	0

 

이처럼 나머지 2~4번노드까지 똑같이 해주면 된다.

 

 

 

 

 

그럼 이제 소스를 살펴보자.

 

FloydWarshel 클래스

public class FloydWarshell {
	
	//플로이드 워셜 알고리즘은 특정 노드를 거쳐갔을때의 최소 비용을 구해주는 프로그램이다.
	//예를 들면 1->3 가는 비용이 12이고 1->2, 2->3 이렇게 2를 거쳐가는 비용이 10이라면 
	// 1->3가는 비용을 1->2, 2->3 가는 비용인 10으로 바꿔주는것이다.
	
	private int[][] graph;
	private int node;
	
	//node를 입력 받으면 해당 node로 2차원 배열을 만들어주는 생성자
	public FloydWarshell(int node) {
		super();
		this.node = node;
		this.graph = new int[node][node];
		for(int i = 0;i<node;i++) {
			for(int j = 0; j<node;j++) {
				if(i == j)
					this.graph[i][j] = 0;
				else
					this.graph[i][j] = 1000;			
			}
		}
	}
	
	public void makeGraph(int start, int end, int cost) {
		this.graph[start][end] = cost; 
	}
	
	public void makeMin() {
		//k는 거쳐가는 노드이다.
		for(int k = 0; k<this.node;k++) {
			//i는 출발 노드이다.
			for(int i = 0; i<this.node;i++) {
				//j는 도착 노드이다.
				for(int j = 0; j<this.node;j++) {
					int bt = this.graph[i][k]+this.graph[k][j];
					int now = this.graph[i][j];
					if( bt < now )
						this.graph[i][j] = bt;
				}
			}
		}
	}
	//그래프 출력
	public void printG() {
		for(int i = 0;i<this.node;i++) {
			for(int j = 0; j<this.node;j++) {
				System.out.print(this.graph[i][j]+" ");
			}
			System.out.println();
		}
	}
}

main 함수

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		PreTest p = new PreTest();
		
		int node = 4;
		FloydWarshell fw = new FloydWarshell(node);
		//간선값 넣기
		fw.makeGraph(0, 3, 8);
		fw.makeGraph(0, 1, 5);
		fw.makeGraph(1, 0, 7);
		fw.makeGraph(1, 2, 9);
		fw.makeGraph(2, 0, 2);
		fw.makeGraph(2, 3, 4);
		fw.makeGraph(3, 2, 3);
		
		
		fw.printG();//그래프 출력
		fw.makeMin();//플로이트워셜 알고리즘 적용
		System.out.println("-------------after--------------");
		fw.printG();//그래프 출력
	}