[알고리즘] 플로이드-워셜 알고리즘

설명 

 그래프 내에 존재하는 두 정점 사이의 최단 경로를 찾는 알고리즘. 모든 정점 쌍에 대한 최단 경로를 계산할 수 있다. 만약 정점의 개수가 n일 경우 n * n크기의 2차원 배열을 생성한 뒤, 각 정점 사이의 거리를 초기화해준다. 이후 그래프 내 모든 정점을 중간 정점으로 사용하여 가능한 경로를 탐색해 나간다. 만약 a에서 b로 가는 경로를 구할 때, 중간 정점을 c라 한다면 a -> c에서 c->b로 가는 경로의 거리와 비교해 최단 거리를 갱신한다. 이 과정을 반복하여 모든 정점 사이의 최단거리를 구한다. 

 

• 시간 복잡도: O(n³) 
• 알고리즘 문제에서는 보통 정점의 개수가 약 100 ~ 1000개 정도로 나온다. 

예시  

• 아래와 같은 그래프의 최단 경로를 구할 경우 

• 먼저 거리의 배열을 초기화 한다.

	1	2	3	4	5
1	0	1	INF	INF	INF
2	1	0	INF	1	INF
3	INF	INF	0	1	INF
4	INF	1	1	0	1
5	INf	INF	INF	1	0

💡자기 자신과의 거리는 0으로 초기화
💡옆 정점까지의 거리를 초기화. 가중치가 없는 경우 위와 같이 표현하지만 만약 경로에 가중치가 있는 경우 가중치로 초기화한다.
💡경로가 존재하지 않는 경우는 무한대(INF) 혹은 아주 큰 값으로 초기화 

• 1번 정점을 중간 정점으로 하는 경우, 거리 갱신(변화 없음)

	1	2	3	4	5
1	0	1	INF	INF	INF
2	1	0	INF	1	INF
3	INF	INF	0	1	INF
4	INF	1	1	0	1
5	INf	INF	INF	1	0

• 2번 정점을 중간 정점으로 하는 경우, 거리 갱신 

	1	2	3	4	5
1	0	1	INF	2	INF
2	1	0	INF	1	INF
3	INF	INF	0	1	INF
4	2	1	1	0	1
5	INf	INF	INF	1	0

           - 4에서 1로 1에서 4로 가는 경로의 값이 갱신된다. 

• 위 과정을 5번 정점까지 반복한다. 
  
  

구현 (수도 코드)

 n: 정점의 개수 
 dist: 최단 거리를 저장하는 배열
 1. dist[i][j]를 무한대 혹은 가능한 정점 사이의 거리의 크기보다 큰 값으로 초기화 해준다. 
 
 2. 입력으로 주어지는 그래프 정점 사이의 거리의 값으로 갱신한다. 
 	이때 두 정점 사이의 경로가 여러 개일 경우 거리가 가장 짧은 경로를 저장한다.  
 
2. 모든 정점 k에 대해 아래의 단계를 수행한다:
   for k = 1 to n:
       for i = 1 to n:
           for j = 1 to n:
               //정점 `k`를 거쳐가는 경로가 더 짧다면, 그 값을 사용해 `dist[i][j]`를 업데이트한다.
               if(dist[i][j] > dist[i][k]+dist[k][j])
               		dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

 

문제 추천

• 백준 11404번 플로이드
• 백준 1753번 최단 경로