[고급 알고리즘] Graph(Shortest Path): Floyd-Warshall

1. Floyd-Warshall

• 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘 입니다. 
• 가중치가 양수 혹은 음수인 그래프에서 사용됩니다. (단, 음의 사이클에는 사용 불가)

 

Dynamic Programming

• 인접행렬을 사용하여 각 정점 쌍 간의 최단 거리를 반복적으로 갱신합니다.

 

2. 동작 원리

• 모든 정점을 경유지로 설정하고, 최단 경로가 경유지를 거쳐 더 짧아질 수 있는지 확인하며 최단 경로 갱신

 

초기화

• 모든 정점 쌍에 대해, 직접 연결된 경로의 거리 초기화
• 자기 자신으로 가는 경로 = 0
• 연결되지 않은 경로 = infinit

 

경유지 검사

• i->j 로 가는 최단 경로가 i -> k -> j로 가는 경로를 통해 더 짧아질 수 있는지 검사 (정점 k를 경유지로 설정)
• 모든 정점에 대하여 반복

 

3. 구현

int[][] dist = {
    {0, 3, INF, 7},
    {8, 0, 2, INF},
    {5, INF, 0, 1},
    {2, INF, INF, 0}
};

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]);
        }
    }
}

Time Complexity: O(V^3)

 

 

출처

• Wiki - Floyd-warshall