Floyd 알고리즘 Java 코드

Floyd

다익스트라 알고리즘은 특정 지점으로 부터 모든 점 까지의 최소 경로를 찾음

이를 vertex 갯수 만큼 반복하면 모든 vertex 사이간의 최소 경로를 찾을 수 있으나 복잡함

floyd 알고리즘은 아주 간결한 코드로 이를 해결 할 수 있음

또한 음수 가중치가 있을 때도 사용 가능(사이클이 없을 경우)

시간 복잡도

O(V^3)

Java code

public class Floyd {
    int vertexNum;
    double adj[][];
    
    void floyd(){
        for(int i=0; i<vertexNum; i++) adj[i][i] = 0; //자기 자신으로 가는 가중치는 0
        for(int k=0; k<vertexNum; k++){
            for(int i=0; i<vertexNum; i++){
                for(int j=0; j<vertexNum; j++){
                    adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
                }
            }
        }
    }
}