[알고리즘 구현] 플로이드 와샬

플로이드 와샬

• 모든 노드로의 최단거리를 알 수 있는 플로이드 와샬

    int fw[n][n];
    
    // 초기화
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i == j)
                fw[i][j] = 0;
            else
                fw[i][j] = MAX;
        }
    }
    for(int i=0;i<costs.size();i++){
       fw[costs[i][0]][costs[i][1]] = costs[i][2];
       fw[costs[i][1]][costs[i][0]] = costs[i][2];
    }
    
    // 실행
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(fw[i][j] > fw[i][k] + fw[k][j])
                    fw[i][j] = fw[i][k] + fw[k][j];
            }
        }
    }