플로이드 워셜 알고리즘(자바)

다익스트라 알고리즘과 같이 한 노선에서 다른 노선으로 가는 최단 거리를 구하는 알고리즘이다.

다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이라면

플로이드 워셜 알고리즘은 모든 노드쌍들의 최단 거리를 구하는 알고리즘이다.

 

** 플로이드 워셜 알고리즘은 음의 간선이 있는 경우에도 사용 가능하다.

 

for (int k = 0; k < n; k++) {  //모든 노드를 한 번씩 중간 노드로 놓고 거리를 갱신
	for(int i = 0; i < n; i++) {
    	for (int j = 0; j < n; j++) {
        	dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

k는 경유지, i는 시작, j 는 도착지이다.

 

예를 들어 1 -> 2 -> 3 이 1번에서 3번으로 가는 최단 거리로 갱신되었다고 하자. 

그럼 5 -> 1 -> 3 경로를 생각할 때 이미 1 -> 3 으로 가는 경로는 1 -> 2 -> 3으로 갱신되어 있기 때문에 

5 -> 1 -> 2 -> 3 경로를 탐색한 것과 마찬가지이다.

즉, k값을 증가시켜주며 모든 노드를 한 번씩 중간에 놓아주면 모든 경로를 탐색할 수 있고, 

따라서 모든 노드에 대해 최단 거리를 구할 수 있다.

 

 

 

 

 

 

참고

[알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm) (tistory.com)

[알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm)