플로이드 워셜 알고리즘 개요, 성능 분석

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

---

 플로이드 워셜 알고리즘 개요

'모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산'한다.
 플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 '거쳐 가는 노드를 기준으로
 알고리즘을 수행'한다.
  -다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않음.
 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.
 다이나믹 프로그래밍 유형에 속한다.

 

 각 단계마다 '특정한 노드 k를 거쳐 가는 경우를 확인'한다
  -a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.

 

 점화식은 다음과 같다.
   D ab = min (D ab, D ak + D kb)
  a에서 b로 가는 거리 = a에서 b로 가는 거리와 a에서 k, k에서 b로 가는 거리를 더한 값 중 비교해 작은 값

 

 

 성능 분석
  노드의 개수가 N개 일 때 알고리즘상으로 N번의 단계를 수행한다.
  -각 단계마다 O(Ne2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다.
  따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(Ne3)이다.
  따라서 일반적으로 노드의 개수가 500개 이하로 잡히는 경우가 많음. (= 시간 문제 때문)

 

 문제 > 전보 문제, 미래 도시  

 

 

---