대엉코딩

0.Transitive Closure

- 그래프 G가 주어졌을 떄 G*은 G와 같은 정점집합(same vertices)을 가진다.

- 만약 그래프 G가 정점 u에서 v로 경로를 가지면 그래프 G*는 정점 u에서 v로 간선(edge)를 가진다.

- Transitive Closure은 경로가 존재하는 지 여부를 알 수 있다.

- 물론 모든 정점에서 DFS를 수행하면 O(n(n+m)) --링크드리스트로 구현되어있다면

  에 알아낼 수 있다.

1. 개요

- 플로이드 워셜 알고리즘은 그래프에서 Transitive Closure을 구하거나

  n:n(다대다) shortest path를 구하는 데 사용 된다.

- Dynamic Programming 알고리즘이다.

- "A에서 B로 갈 수 있고 B에서 C로 갈 수 있는데 AC간선이 없다면, 간선을 연결해준다."

2.아이디어

- 모든 정점들을 번호로 관리한다.

- n단계로 구성되어 차례차례 확장해나가는 구조.

- k번째 단계의 수행이 완료되면, 1~k까지의 간선들은 모두 활용한 것 이다.

- 친구들끼리 연락을 해야하는 상황을 생각해보면 이해가 쉽다.

   (난 A의 전화번호를 모르지만 B의 번호를 알고있다. B는C의 번호를알고있다.

     그럼 난 두 단계를 거치면 C의 번호를 알게된다.)

3.The Floyd-Warshall Algorithm(플로이드 워셜 알고리즘)

- 각 단계의 그래프를 G0,G1,.......Gn이라 하자.

- 정점들은 v1,v2,.....,vn이라 한다.

- k단계에서 Gk는 Gk-1으로 부터 계산한다.

- 수행시에 adjacent연산을 많이 쓰는데 (두 정점 사이에 경로가 있는지 u->v)

   그럼 Graph를 구현 할 때 인접행렬로 구현하는 게 좋겠죠~

- 전화번호 예시에 빗대어 설명하였습니다.

-그럼 n:n shortes path는 어떻게 구하느냐??
- 기본적인 원리는 위와 같습니다만, 새로 알게된 경로가 기존의 경로보다 짧을 경우에 그 값을 넣어주고

   그렇지 않은 경우는 update하지 않습니다.

- 처음 초기화를 무한대로 해줍니다.

4.Example

(1)

(2)

(3)

(4)

(5)

5. 분석(Analysis)

- n:n shortest path를 구할 때 n번의 다익스트라 알고리즘을 호출하면 O(nmlogn)의 시간 복잡도를 가진다.

- 플로이드 워셜 알고리즘은 O(n*3)의 시간 복잡도를 가진다.