FloydWashall 알고리즘

 

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다.

이 알고리즘의 핵심은 '거쳐가는 정점'을 기준으로 판단하는 것이다. 쉽게 말해 i->j로 이동 시 i->k->j의 방식이 가능한지에 대한 판단을 하는 것이다. 이 알고리즘은 3중 for문을 이용하여 시간복잡도는 O(N^3)으로 비교적 속도가 오래걸리지만 input의 범위가 작은 경우 쉽게 문제를 해결할 수 있는 알고리즘이다.

 

import java.util.Scanner;

public class floydWarshall {
	static int INF = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();

		int[][] ary = new int[a][a];

		for (int i = 0; i < a; i++) {
			for (int j = 0; j < a; j++) {
				ary[i][j] = sc.nextInt();
				if (i != j && ary[i][j] == 0) {
					ary[i][j] = INF;
				}
			}
		}

		for (int k = 0; k < a; k++) {// k는 경유지
			for (int i = 0; i < a; i++) {
				if (i == k) {
					continue;
				} // 경유지가 출발지이면 통과
				for (int j = 0; j < a; j++) {
					if(i==j || j==k) {
						continue;//도착지가 출발지나 경유지인 경우 통과
					}
					if(ary[i][k] + ary[k][j] < ary[i][j]) {
						ary[i][j] = ary[i][k] + ary[k][j];
					}
				}
			}
		}
	}
}