<aside> 💡 참고하여 작성함 → https://chanhuiseok.github.io/posts/algo-50/

</aside>

플로이드-워셜 알고리즘 O(N^3)

다익스트라 : 지정한 하나의 노드에서 다른 모든 노드까지의 최단 거리를 구할 수 있음

플로이드-워셜 : 모든 노드 간 최단 거리를 구할 수 있음 (시간이 오래걸림)

위와 같은 그래프가 있을 때

노드 간의 최소 거리를 구하고 싶다면

1. 2차원 인접행렬을 만들어줌 (없는 노선은 INF로 표시함)
2. 노선이 있다면 가중치를 입력

각각의 노드를 중간 노드로 하여 계산

1. 1번 노드를 중간노드로 하여 계산함
2. 2-[1]-4 노드를 연결함 (가중치는 합연산)
3. 2-[1]-5 노드를 연결함 (””)

1. 위와 같은 방법으로 2번 노드를 중간노드로 하여 계산해준다.