플로이드-워셜 알고리즘

플로이드-워셜 알고리즘

그래프 상에서 가능한 모든 노드 쌍들에 대해 최단 거리를 구하는 알고리즘이다.

같은 최단 거리 알고리즘인 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구할 수 있고, 음의 가중치를 가진 간선이 그래프에 있어도 적용할 수 있다는 것이 특징이다.

시작 노드, 경유지, 도착 노드에 대해 반복문을 돌아야하기 때문에 시간 복잡도는 O(V^3) 이다.

코드

import java.util.*;

public class FWAlgorithm {

	static final int INF = 987654321;
	static int N, distance[][];
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		distance = new int[N][N];
    // 입력은 인접 행렬로 주어진다.
		for(int i=0; i<N; ++i) {
			for(int j=0; j<N; ++j) {
				distance[i][j] = sc.nextInt();
				if(i != j && distance[i][j]==0) {
          //자기자신으로의 인접 정보가 아니고 인접해있지 않다면 INF로 채우기
					distance[i][j]=INF;
				}
			}
		}

		for (int k = 0; k < N; k++) { // 경유지
			for (int i = 0; i < N; i++) { // 시작 노드
				for (int j = 0; j < N; j++) { // 도착 노드
          distnace[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
				}
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(distance[i][j] + " ");
			}
			System.out.println();
		}

	}


}