플로이드-워셜 알고리즘에 대해 설명해보세요.

---

플로이드 워셜의 작동 방식

• DP에 해당하는 알고리즘으로, 모든 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘이다.
  1. 모든 노드 간의 최단 거리를 저장할 2차원 행렬을 만든다. 자기 자신은 모두 0으로, 연결되지 않은 노드는 임의의 큰 값으로 초기화 한다.
  2. 1번 노드부터 4번 노드까지 각 노드를 거쳐 가는 경우를 고려하여 행렬을 업데이트한다. 거쳐가는 노드이므로 선택된 노드와 연결된 간선은 업데이트 되지 않는다.
  
  
  
  

---

플로이드 워셜의 특징

• 시간 복잡도
  : 노드의 수가 N일때, N번의 탐색을 해야하며 각 탐색마다 N^2의 연산으로 최단 경로를 업데이트하므로 O(N^3)의 시간 복잡도를 가진다.

• 공간 복잡도
  : 최단 거리를 저장할 2차원 배열이 필요하므로 O(N^2)의 공간 복잡도를 가진다.

• 장점

  • 다익스트라에 비해 구현이 쉽고 간단하다.
  • 음수 간선이 있는 그래프에서 사용할 수 있다.

• 단점
  : 모든 노드간의 최단 거리를 구하기 때문에 시간이 오래걸리고 다익스트라보다 많은 메모리 공간을 필요로 한다.

---

결론

플로이드 워셜 알고리즘은 DP에 해당하는 알고리즘으로, 모든 노드 간의 최단 거리를 구할 때 사용하는 방법입니다. 최단 거리를 저장하는 2차원 배열을 만들어서 모든 노드를 거치면서 노드 간의 최단 거리를 업데이트하면서 최종적으로 최단 거리가 저장된 2차원 배열을 만들게 됩니다. 이 때 음수 간선은 포함해도 되나, 음수 사이클은 없어야 한다. 다익스트라에 비해 구현이 쉽고 간단하지만 그 만큼 성능이 떨어지고 많은 메모리 공간을 필요로 합니다. O(N^3)의 시간 복잡도를 가지며, O(N^2)의 공간 복잡도를 가집니다.