플로이드워셜(FloydWarshall) 알고리즘

FloydWarshall 알고리즘

FloydWarshall(플로이드워셜) 이란

• 그래프에서 모든 정점에서 모든 정점으로의 최단경로를 구하는 알고리즘
• 시간복잡도 O(N^3)
• 한 출발점에서 어떤 한 도착점까지 갈 수 있을 때, 갈 수 있는 경로 중 최단경로가 되는 값을 구한다
  • 출발점과 도착점 사이의 경유지를 거쳐갈 경우를 고려해 최단경로를 파악한다

ex) 2 -> 4로 갈 수 있는 경로. 2->3->4(11) , 2->1->4(9) 이므로 9가 선택되야함.

사진출처 : kdb.velog

FloydWarshall(플로이드워셜) 구현 방법

1. 2차원 배열에 그래프의 간선 정보를 저장 (직접 연결되어 있지 않으면 무한, 자기 자신으로 가는 거리 0)

        for(int i=0;i<N;i++) {
            Arrays.fill(road[i], INF);
            road[i][i] = 0;
        }

2. 모든 정점을 경유지로 정하고 출발점-경유지-도착점과 기존 배열에 저장된 출발점-도착점 값을 비교

for(int k=0;k<N;k++){ // 경유지 k
  for(int i=0;i<N;i++){ // 출발점 i
    for(int j=0;j<N;j++){ // 도착점 j
        if(road[i][j]>road[i][k]+road[k][j])
          road[i][j] = road[i][k]+road[k][j];
    }
  }
}

플로이드워셜 알고리즘을 언제 사용?

• 모든 최단 경로를 알고 싶을 때
• 경로의 유무를 알고 싶을 때

백준 2458 키순서

백준 경로찾기