플로이드 워셜 (Floyd Warshall)

public class Floyd_Warshall {  

    static final int _M_size_ = 100; // max number of vertices  
    static final int _INTMAX_ = 1000000000; // infinite  

    static int AdjMatrix[][] = new int[_M_size_][_M_size_];  // Adjacent matrix  
    static int dist[][] = new int [_M_size_][_M_size_]; // Shortest distance matrix  

    static void floyd_warshall(int V) {  

    for(int i = 1 ; i <= V ; i++)
        for(int j = 1 ; j <= V ; j++)
            if(AdjMatrix[i][j] != _INTMAX_) dist[i][j] = AdjMatrix[i][j];
            else dist[i][j] = _INTMAX_;               

        for(int k = 1 ; k <= V ; k++) {  
            for(int i = 1 ; i <= V ; i++) {  
                for(int j = 1; j <= V ; j++) {  
                    if(dist[i][j] > dist[i][k]+dist[k][j]) {  
                        dist[i][j] = dist[i][k]+dist[k][j];  
                    }  
                }  
            }  
        }  
    }  

}