Data Structure - Graph ( Floyd-Warshall Algorithm && Transitive Closure )

Floyd-Warshall Algorithm

플로이드-워셜 알고리즘이란

• 모든 최단 경로를 구하는 알고리즘으로서 정점을 기준으로 하는 알고리즘을 말합니다.

다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이였다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다.

모든 노드 간의 최단거리를 구해야 하므로 2차원 adjacent matrix를 구성합니다. 알고리즘은 여러 라운드로 구성됩니다. 라운드마다 각 경로에서 새로운 증간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복해야 합니다.

이를 간단한 코드로 짜보면 다음과 같을 수 있겠습니다.

...
	for(int k = 0; i < n; k++) {
    	for(int i = 0; i < n; i++) {
        	for(int j = 0l j < n; j++) {
            	distance[i][j] = min(distance[i][k]+distance[k][j], distance[i][j]);
            }
        }
    }
...

구현의 핵심 부분에 3중 for문이 있으므로 시간 복잡도는 O(n^3)이 됩니다.

 

Transitive Closure

Transitive Closure 즉 추이 클로저는 간단한 개념입니다. 다른 edge를 통해서 갈 수 있는 vertex도 adjacent matrix에 적어주면 됩니다. 그리고 A+와 A*의 차이점은 자기 자신으로 갈 수 있다는 것을 표기 할 것인가, 아니면 안 할 것인가 밖에 없습니다.