[Algorithm] Floyd Warshall-1

 

플로이드 워셜 알고리즘

다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

만약 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘을 사용해야 한다.

 

public class FloydWarshall {
	
	// 플로이드 워셜 알고리즘
	// 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
	// 만약 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘을 사용해야 한다.
	
	static int number = 4;
	static int INF = 100000000;
	static int[][] originArr = {{0, 5, INF, 8}, {7, 0, 9, INF}, {2, INF, 0, 4}, {INF, INF, 3, 0}}; // 자료 배열 초기화
	
	public static void floydWarshall() {
		int[][] renewArr = new int[number][number]; // 결과 배열 초기화
		
		for (int i = 0; i < number; i++) {
			
			for (int j = 0; j < number; j++) {
				renewArr[i][j] = originArr[i][j]; // 결과 배열을 초기 자료 배열과 동일하게 만들어 준다.
			}
		}
		
		// k : 거쳐가는 노드
		for (int k = 0; k < number; k++) {
			
			// i : 출발 노드
			for (int i = 0; i < number; i++) {
				
				// j : 도착 노드
				for (int j = 0; j < number; j++) {
					
					if (renewArr[i][k] + renewArr[k][j] < renewArr[i][j]) { // k 노드를 거쳐갈 때 거리 값이 더 작다면
						renewArr[i][j] = renewArr[i][k] + renewArr[k][j]; // i 노드에서 j 노드로 가는 최단 거리 갱신
					}
				}
			}
		}
		
		for (int i = 0; i < number; i++) {
			
			for (int j = 0; j < number; j++) {
				System.out.print(renewArr[i][j] + " "); // 결과 배열 출력
			}
			
			System.out.println();
		}
	}

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

Floyd Warshall 알고리즘 문제 풀이 Java