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

1. Floyd-Warshall

• 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘 입니다. 
• ✅ 음수 가중치가 허용됨
• ❌ 음의 사이클에는 사용 불가

 

2. 동작 원리

• 모든 정점을 경유지로 설정
• ✅ 최단 경로가 경유지를 거쳐 더 짧아질 수 있는지 확인
• ➡️ 각 정점 쌍 간의 최단 거리를 반복적으로 갱신합니다. (Dynamic Programming)

 

초기화

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

 

경유지 검사

• i->j 로 가는 최단 경로가 경유지를 통해  더 짧아질 수 있는지 검사
• ✅ 정점 k를 경유지로 설정

 

3. 구현

int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
    Arrays.fill(dist[i], INF);
    dist[i][i] = 0;
}

for (int[] edge : edges) {
    int s = edge[0], d = edge[1], w = edge[2];
    
    dist[s][d] = w;
}

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
    	if (dist[i][k] == INF) continue;
        for (int j = 0; j < n; j++) {
            if (dist[k][j] == INF) continue;
            dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

Time Complexity: O(V^3)

 

 

출처

• Wiki - Floyd-warshall