플로이드 알고리즘(All pair shortest path) 자바로 구현

플로이드 알고리즘

어떤 정점에서 시작해서 다른 정점으로 가는 최단경로를 구함. (모든 정점에 대해서)

알고리즘 동작 과정

0번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

1번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

2번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

3번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

4번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

5번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

6번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

를 모두 구할것이다. 

처음에는 0번 정점만을 거칠수 있을때 

0번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

1번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

2번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

3번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

4번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

5번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

6번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

를 모두 인접행렬에 갱신한다.

그다음 0번과 1번정점만을 거칠수 있을때

0번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

1번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

2번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

3번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

4번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

5번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

6번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

를 구하게 된다

이런식으로 차례대로 0번,1번,2,3,4,5,6번을 모두 거칠수 있을때

0번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

1번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

2번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

3번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

4번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

5번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

6번에서 0,1,2,3,4,5,6번 정점까지 가는 최단경로

를 구하게 되면 최종적으로 모든 정점을 거칠수 있을때 X정점에서 Y정점으로 가는 최단경로로 인접행렬이 갱신되게 되는것이다.

이것이 가능한 이유는 다음과 같다.

0번 정점에서 3번정점까지 가는 최단경로를 구하려고 한다. 

1번정점까지 징검다리로 사용할수 있다고 했을때 인접행렬값에 0->1->3 또는 0->3 중 최소값이 최단경로로 들어가있을것이다.

2번정점까지 징검다리로 사용할수 있다고 추가된 경우 0->1->2->3이 최단경로인지 0->1->3이 최단경로인지 판단해서 인접행렬값이 갱신된다.

2번정점을 거친것이 더 짧은 경로가 될것인가 아니면 2번정점을 거치지 않고 1번정점만을 이용해서 3번정점까지 가는것이 최단경로가 될것인가를 결정하는것이다. 

자바로 짠 플로이드 알고리즘 코드

 
public class floyd {
    int INF = 9999;
    int w[][] = {{0,7,INF,INF,3,10,INF},
                 {7,0,4,10,2,6,INF},
                 {INF,4,0,2,INF,INF,INF},
                 {INF,10,2,0,11,9,4},
                 {3,2,INF,11,0,INF,5},
                 {10,6,INF,9,INF,0,INF},
                 {INF,INF,INF,4,5,INF,0}}; //그래프는 7개의 정점을 가진다. 비방향그래프.}
    public void printmatrix() {
        for(int i=0; i<7; i++) {
            for(int j=0; j<7; j++) {
                if(w[i][j] == INF) {
                    System.out.printf(" INF"); continue;
                }
                System.out.printf("%4d",w[i][j]);
            }
            System.out.println();
        }
    }
    public void floydalgorithm() {
        for(int k=0; k<7; k++)
        {
            for(int i=0; i<7; i++)
            {
                for(int j=0; j<7; j++)
                {
                    if(w[i][j]>w[i][k]+w[k][j])
                        w[i][j] = w[i][k]+w[k][j];
                }
            }
            System.out.println(k +"번째 정점까지만 거칠수 있는 경우 모든 쌍에 대한 최단경로");
            printmatrix();
        }
    }
    public static void main(String[] args) {
        floyd f = new floyd();
        f.floydalgorithm();
    }
 
}