12-2 플로이드 와샬 알고리즘

1. 플로이드 와샬 알고리즘

① 플로이드 와샬 알고리즘 : 최단 경로를 구하는 알고리즘인 플로이드 와샬 알고리즘은

                                             가능한 모든 노드 쌍들에 대한 최단 거리를 구하는 알고리즘

 

  - 그래프에서 모든 정점 사이의 최단거리(4)를 구하기 위한 알고리즘

 

② 다익스트라 알고리즘과 플로이드 와샬 알고리즘 비교

③ 그래프의 탐색 방법

 

2. 플로이드 와샬 알고리즘의 적용방법

① 플로이드 와샬 알고리즘

③ 플로이드 와샬 알고리즘 수행시간

 -> 모든 정점 간 경로의 최소 비용을 구하는 것은 O(|V^3|)의 시간 복잡도 가짐

 

④ 이행폐쇄  :  거쳐서 갈 수 있는 모든 곳을 직접 가는 간선으로 연결한 그래프

  - 간선의 추가를 통해 대부분의 노드들이 인접 노드로 바뀌게 되며 인접 행렬로 표현하는 것이 편리

3. 플로이드 와샬 알고리즘의 적용 예

①