[알고리즘] Floyd Warshall

개념

그래프에서 모든 노드 사이의 최단 경로의 거리를 구하는 알고리즘
동적계획법을 사용하여 접근
경유 노드를 설정하여 최소비용 구할 수 있다.
시간복잡도 : O(n^3)

코드

public void floydalgorithm() {
        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(w[i][j]>w[i][k]+w[k][j])
                        w[i][j] = w[i][k]+w[k][j];
                }
            }
        }
    }