플로이드 워셜

플로이드 워셜

다익스트라는 그래프 내의 한 시작점 으로 부터 다른 노드까지의 최단거리를 구한다면
플로이드 워셜은 모든 노드간의 최단 거리를 구한다.
다익스트라 거리 리스트는 1차원(노드가 N일때 사이즈는 N)
플로이드 워셜의 경우 거리 리스트는 2차원(N*N)이다.

시간복잡도

하나의 노드(현재 갱신하고 있는 노드)에 대하여 그 노드를 제외한 N-1P2의 연산을 가지므로
O(N*N-1P2) => O(N^3)의 시간 복잡도를 가진다.

점화식

Dab = min(Dab,Dak+Dkb): a노드에서 b노드 까지의 최단 거리는
현재 참조하고 있는 k노드를 거쳐 가는 비용과 비교 하여 더 작은 것으로 갱신한다.

코드

class Main {
  static int[][] data = {
    // {a,b,c} == 노드 a에서 b까지 연결 되어있고 비용이 c로 연결
    {1,2,4},
    {1,4,6},
    {2,1,3},
    {2,3,7},
    {3,1,5},
    {3,4,4},
    {4,3,2},
  };
  static int N=4,E=7; // vertex, edge 갯수
  static int INF = 1004;
  static int[][] graph = new int[N+1][N+1];
  
  public static void main(String[] args) throws IOException{
    // 그래프 거리 비용 초기화
    for (int i=1; i<N+1; i++){
      for (int j=1;j<N+1; j++){
        if(i == j) graph[i][j] = 0;//출발점과 도착점이 같으면 비용이 0
        else graph[i][j] = INF; 
      }
    }
    //간선정보 입력
    for(int i=0; i<E; i++){
      int[] cur = data[i];
      int s=cur[0],e = cur[1], cost = cur[2];
      graph[s][e] = cost;
    }
    //플로이드 워샬 알고리즘 적용
    for(int k=1;k<N+1; k++){
      for(int i=1; i<N+1; i++){
        for(int j=1; j<N+1; j++){
          //만일 k ==i or k==j 인 경우 0으로 나오기때문에 따로 분기 처리할 필요없다.
          graph[i][j] = Math.min(graph[i][j],graph[i][k]+graph[k][j]);
        }
      }
    }

    for (int i=1; i<N+1; i++){
      for (int j=1; j<N+1; j++){
        int cur = graph[i][j];
        if (cur == INF) System.out.print("INF ");
        else System.out.print(graph[i][j]+" ");
      }
      System.out.println();
    }
    
  }

}

출력:
0 4 8 6
3 0 7 9
5 9 0 4
7 11 2 0