11404 플로이드

 

 

 

1. 플로이드 워셜 알고리즘에 대해 설명하자면,

모든 정점에서 모든 정점으로의 최단경로를 구하고 싶을 때 사용한다.

=> 거쳐가는 정점 기준으로 알고리즘 수행

=> 음수 순환 사이클이 없는 그래프에서 수행

 

2. 다익스트라 알고리즘은, 하나의 정점에서 출발하여 다른 모든 정점으로의 최단경로 구함.

 

 

 

 

 

그러면 플로이드 워셜 알고리즘에 대해 알아보자. 

 

1. 첫번째

 

맨 처음에 직행으로 갈 수 있는 경로를 구하면, 아래 표와 같다.

갈 수 있는 경로가 없다면, 무한(큰 값)으로 둔다.

 

1->1,  2->2,  3->3 

즉 본인에서 본인으로 가는 경로는 0으로 한다. 

	1	2	3
1	0	1	1
2	1	0	4
3	5	무한	0

 

 

 

 

2. 두번째 - 정점 1을 경유하여,

위에서 플로이드 워셜 알고리즘은 거쳐가는 정점 기준으로 수행한다고 했다. 

정점을 순서대로 돌아가며, 최단경로를 구한다.

 

정점 1을 경유하는 경우는 아래와 같다.

[1] 3 - 1 - 2

[2] 2 - 1 - 3

 

 

 

[1] 3 - 1 - 2 의 경우 

총 거리가 5 + 1 = 6 이다.

그런데 원래 3 -2 의 경우 무한이므로,

6이 더 작은 값이다. 

 

따라서 무한 -> 6로 바꿔준다. 

 

[2] 2 - 1 - 3 의 경우 

총 거리가 1 + 1 = 2이다.

원래 2 -3 의 경우 4이므로 정점을 지나가는 것이 더 작아서 4-> 2로 바꿔준다 

 

 

	1	2	3
1	0	1	1
2	1	0	4 -> 2
3	5	무한 -> 6	0

 

2. 세번째 - 정점 2를 경유하여,

정점 2를 경유하는 경우는 아래와 같다.

 

 

[1] 1 - 2 - 3

이 경우 총 거리가 1 + 4 = 5 이다.

그런데 1 - 3의 경우 1이므로 원래의 경로가 더 작다.

바꿔줄 것 없이 그냥 넘어가면 된다. 

 

	1	2	3
1	0	1	1
2	1	0	2
3	5	6	0

 

2. 네번째 - 정점 3을 경유하여,

 

 

 

이 경우는 

[1] 2 - 3 - 1 

 

[1] 의 경우 총 경로가 4 + 5 = 9

2 - 1 의 경로는 1이므로 원래 경로가 더 작다.

그러므로 그냥 유지하면 된다. 

 

	1	2	3
1	0	1	1
2	1	0	2
3	5	6	0

 

 

이런식으로 해결하면 된다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {	
	
	private static final int max = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {		
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine(), " ");
		int m  = Integer.parseInt(st.nextToken());
		
		int bus[][] = new int [n+1][n+1];
		
		for(int i=1; i<=n; i++) {			
			for(int j = 1; j<=n; j++) {
				
				if(i==j) {						
					bus[i][j] = 0;						
					
				}else {									
					bus[i][j] = max;
					
				}
			}			
		}	
		
		for(int i=0; i<m; i++) {
			
			 st = new StringTokenizer(br.readLine(), " ");
			 int a = Integer.parseInt(st.nextToken());
			 int b = Integer.parseInt(st.nextToken());
			 int c= Integer.parseInt(st.nextToken());			 
	
			 bus[a][b] = Math.min(c, bus[a][b]);
			
			
		}	
	
		
		for(int i=1; i<=n; i++) {
			for(int j =1; j<=n; j++) {
				for(int k =1; k<=n; k++) {
					
					if(bus[j][i]!=max && bus[i][k]!= max ) {
					bus[j][k] = Math.min(bus[j][k], bus[j][i] + bus[i][k]);
					
					}					
				}			
			}			
		}
		
		
		
		for(int i=1; i<=n ; i++) {
			for(int j = 1; j<=n ; j++) {
				
				int value = bus[i][j];
				
				if(value==max) {
					value = 0;
				}
				
				System.out.print(value + " ");
			}System.out.println();
		}
		
	
	
	}
	
	
	
}

 

 

 

 

 

 

 

 

 

참고 블로그 : 

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

https://olrlobt.tistory.com/43

[알고리즘] Floyd-Warshall Algorithm : 플로이드 워셜 알고리즘이란?